Folien Komplexitätstheorie 2005/2006

• 51: Für beliebige x darf Lösungsmenge S(x) nicht leer sein.
• 104: "<=_{PTAS}" ist wegen fehlender Antisymmetrie keine partielle Ordnung auf den Problemen, wie ursprünglich behauptet, wohl aber auf den Äquivalenzklassen bez. der zugehörigen Relation "=_{PTAS}" (siehe korrigierte Folie). (Silke Hochgräber)
• 112, 121: Definition von NPO: Lösungswerte müssen ganzzahlig sein.
• 296: Bei Vernachlässigbarkeit "n groß genug" ergänzt. (Thomas Hofmeister)
• 301: Bit Commitment: Es reicht, wenn Bob kein k' mit c(1-b,k') = c(b,k') effizient berechnen kann (anstatt der ursprünglichen Forderung, dass ein solches k' nicht existiert). (Markus Strauch)
• 449: Simulationsprogramm stoppt innerhalb der Wiederholungsschleife nur, wenn ursprüngliche Maschine akzeptiert. Siehe Korrektur auf der Folie. (Mathias Schwarzhoff)
• 740: Folie weg (da Definitionen nicht mehr benötigt), dafür in der Vorlesung erwähntes Ergebnis von Kabanets-Impagliazzo (Derandomisierung => superpolynomielle SK-Schranken) als neue, vorletzte Folie.