Komplexität von Entscheidungsproblemen Ein Seminar

Einleitung....Pages 1-10
I. Zeitlich beschränkte Turingmaschinen und polynomiale Reduktion....Pages 11-19
II. Polynomial beschränkte nichtdeterministische Turingmaschinen und die Vollständigkeit des aussagelogischen Erfüllungsproblems....Pages 20-35
III. Probleme, die zum Erfüllungsproblem der Aussagenlogik polynomial äquivalent sind....Pages 36-48
IV. Weitere zum Erfüllungsproblem polynomial äquivalente kombinatorische Aufgaben....Pages 49-71
V. Ein polynomialer Algorithmus zur Bestimmung unabhängiger Repräsentantensysteme....Pages 72-85
VI. Polynomiale Transformationen und Auswahlaxiom....Pages 86-101
VII. Spektralproblem und Komplexitätstheorie....Pages 102-126
VIII. Untere Schranken für die Komplexität log. Entscheidungsprobleme....Pages 127-137
IX. Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper....Pages 138-162
X. Simulation von Turingmaschinen mit logischen Netzen....Pages 163-181
XI. Längen von Formeln....Pages 182-217