2η Φάση

• Parallel Computation (classes NC, RNC, AC, TC, the PRAM model and the Isolating Lemma)
• Alternation
• Quantum Computation
• Zero-knowledge (I. Παπαϊωάννου)
• Pseudorandomness & Derandomization
• Algebraic Computation
• PCPs, Inapproximability, Discrete Fourier Analysis (Λ. Ζακυνθινού & Δ. Τσίπρας)
• Communication Complexity
• Average-Case Complexity (M. Σάμαρης)

1η Φάση

-- Reductions & NP-Completeness: Different types of reductions and relations among them, NP-completeness

-- NP-complete Problems: Cook's Theorem, SAT and Satisfiability variants (Παπαμακάριος)

• p.171-172 & 183-188 από το [1]

-- NP-complete Problems: IS, CLIQUE, MAX-CUT (Πετροπαναγιωτάκη)

• p.188-193 από το [1]

-- NP-complete Problems: HP, TSP, 3COL, 0/1IP (Διαμαντής)

-- NP-complete Problems: 3DM, Knapsack, Pseudopolynomial Algorithms and Strong NP-completeness (Λιβιεράτος)

• p.199-206 από το [1]

-- Ladner's Theorem, Density, Sparse Sets (Βελώνα)

• p.329-332 & p.336-339 από το [1]

-- The "Berman-Hartmanis" Conjecture, NP-isomorphism, padding (Ζαμπετάκης)

-- Second-Order Logic, Undecidability-Incompleteness, Fagin’s Theorem (Κωτσάνη)

-- Function Problems: The classes coNP and ΔNP, Function classes and reductions, the classes PLS and PPAD. (Σκουλάκης)