By Dana Moshkovitz


3-colorability (and related stories) Independent Set (Trip), Hamiltonian Cycle; Problem interrelated - NP-complete, aproximation: next best

(Space Bounded computations, Reachability ;Formal Definition: Graphs, algorithmic problems
(3-colorability, Independent-Set, Vertex-Cover))


Turing Machines, NonDeterministic Turing Machines; Exponential Slow-down Simulation; Bounds on Resource (Time, Space, ...): NP, P (e.g. Linear Equations?) ( Reductions

Pseudo Code; Various models)

Cook’s Theorem: SAT is NP-Complete Go!
More NP-Complete Problems: 3SAT, CLIQUE, Hamilton-Cycle, Subset-Sum, Max-Cut Go!
Approximation Algorithms for NP-hard Problems Go!
The Traveling Salesperson Problem Go!
The complexity class coNP Go!
Pratt’s Theorem: PRIMESNPcoNP Go!
Savitch's Theorem: NSPACE(f(n))=SPACE(f(n))  
The complexity class PSPACE  
NL, Immerman's Theorem: NL=coNL  
Polynomial-Time Hirerchy (PH)  
Hardness of Approximation
Randomized Complexity Classes (BPP,ZPP,RP)  
Interactive Proofs (IP), Zero Knowledge Proofs (ZKP)  
The complexity class #P