Section outline

  • Δευτέρα

      • Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.
      • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem


      Πέμπτη

      • Non-Uniform Complexity: Uniform circuit families and parallel computations (S. Zachos)


      Μπορείτε να διαβάσετε:
      • Sections 7.1-7.5 from [2]