By Dana Moshkovitz

 Introduction: 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)) Go! Preliminaries: Turing Machines, NonDeterministic Turing Machines; Exponential Slow-down Simulation; Bounds on Resource (Time, Space, ...): NP, P (e.g. Linear Equations?) (http://www.igs.net/~tril/tm/tm.html Reductions Pseudo Code; Various models) Go! 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: PRIMESÎNPÇcoNP 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