Items related to Komplexität von Entscheidungsproblemen: Ein Seminar:...

Komplexität von Entscheidungsproblemen: Ein Seminar: 43 (Lecture Notes in Computer Science, 43) - Softcover

 
9783540078050: Komplexität von Entscheidungsproblemen: Ein Seminar: 43 (Lecture Notes in Computer Science, 43)

Synopsis

I. Zeitlich beschränkte Turingmaschinen und polynomiale Reduktion.- II. Polynomial beschränkte nichtdeterministische Turingmaschinen und die Vollständigkeit des aussagelogischen Erfüllungsproblems.- III. Probleme, die zum Erfüllungsproblem der Aussagenlogik polynomial äquivalent sind.- IV. Weitere zum Erfüllungsproblem polynomial äquivalente kombinatorische Aufgaben.- V. Ein polynomialer Algorithmus zur Bestimmung unabhängiger Repräsentantensysteme.- VI. Polynomiale Transformationen und Auswahlaxiom.- VII. Spektralproblem und Komplexitätstheorie.- VIII. Untere Schranken für die Komplexität log. Entscheidungsprobleme.- IX. Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper.- X. Simulation von Turingmaschinen mit logischen Netzen.- XI. Längen von Formeln.

"synopsis" may belong to another edition of this title.