Komplexitätstheorie

Vorlesung vom Wintersemester 98/99

• Platzkomplexität (Satz von Savitch, PSPACE, PSPACE-Vollständigkeit (QBF, generalized geography), NL-Vollständigkeit, NL = co-NL)
• Hierarchiesätze und EXSPACE-Completeness
• Approximationalgorithmen (Max-Cut, Zusammenhang mit linearem Programmieren)
• Probabilistische Algorithmen (Primalität, Schwarz-Zippel, Äquivalenz von Read-Once Branching Programs),
• Schaltkreiskomplexität
• Kommunikationskomplexität, Trennung von probabilistischen und deterministischen Algorithmen, Rankschranke)
• Interactive Proof Systeme, Definition, Beispiele (Graphisomorphie, Graphnichtisomorphie, #SAT) IP = PSPACE
• PCP (probabilistically checkable proofs), NP ist enthalten in PCP[poly,1].
• Nichtapproximierbarkeit von Max-Sat.

Sipser: Introduction to the Theory of Computation Motwani-Raghavan: Randomized Computation

Bitte auf jeden Fall den übergeordneten Abschnitt lesen.