Εισαγωγή - Διαδικαστικά Hierarchies of Complexity Classes

Computational Models, Hierarchies, History

Computational Model-Turing Machines: Equivalence of Computational Models, Turing Machines, Time and Space bounds, multiple strings, linear speedup, nondeterminism.

Computability and Undecidability: The Universal Turing Machine, Simulation, Diagonalization, The Halting Problem, Recursive and Recursive Enumerable Sets.

Complexity Classes: Complexity measures, Time and Space Classes Hierarchy Theorems, Gap Theorem, Basic inclusions between complexity classes, Quantifier Notation and characterization of NP (Theorem 9.1 [1]).

Space Computation: The classes L and NL, Savitch’s Theorem, Immerman-Szelepscényi Theorem (NL=coNL), Reingold’s Theorem: L=SL (without proof) & Undirected REACHABILITY.

Second-Order Logic, Incompleteness, Fagin's Theorem

Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd)

Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd). The Arithmetical Hierarchy.

Diagonalization & Hierarchies, Case-Study: DTIME(n)⊂DTIME(n^1.5) Reductions: Reductions between problems, P-completeness, NP-completeness.

Reductions: Different types of reductions (Karp, Cook, Cook[1], tt), and relations among them. NP-Complete Problems: - Cook’s Theorem, SAT and satisfiability variants - IS,CLIQUE, MAX-CUT

NP-Complete Problems: - HP, TSP, 3COL, 0/1 IP - 3DM, KNAPSACK, Pseudopolynomial Algorithms and Strong NP-Completeness

Ladner’s Theorem, Density, Sparse sets The “Berman-Hartmanis” conjecture, NP-isomorphism, padding.

Function Problems: The classes coNP and ∆NP, Function classes (FL, FP, FNP, FPSPACE etc) and reductions, the classes PLS and PPAD.

Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP classes.

Oracles & The Polynomial Hierarchy: Oracles and oracle classes, the Polynomial-Time Hierarchy.

Quantifier notation (∃+) and related results, semantic and syntactic classes, the “P vs BPP” question.

2o Quiz σε Reductions & Randomized Complexity Classes. The equivalence between Oracle and Quantifier Polynomial Hierarchy

The Polynomial-Time Hierarchy and related theorems, The BPP Theorem, Swapping quantifiers, Operator-defined classes.

Non-Uniform Complexity: Boolean circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs.

Parallel computation (classes NC, RNC, AC, TC)

Interactive Proof Systems:

-Interactive Proofs (IP)

Interactive Proof Systems:

-Arthur-Merlin Games (AM)

Interactive Proof Systems:

-Shamir’s Theorem: IP=PSPACE

-Zero Knowledge Proofs

Quantifier Notation and Arthur-Merlin Games

An introduction to Pseudorandomness and Derandomization

Introduction to PCPs

Interactive Proof Systems:

-Probabilistically Checkable Proofs (PCP)

-Dinur's Proof of the PCP Theorem

Counting Complexity: #P, #P-completeness, Toda's Theorem, Gaps

Approximability and Approximation Schemes

Reingold's Theorem: L=SL

Quantum Computation

Alternation

Interactive Proof Systems: -Hardness of Approximations

Pseudorandomness & Combinatorial Constructions

The Unique Games Conjecture

Algebraic Computation

The Bright Side of Hardness