Komplexität von Entscheidungsproblemen

Ein Seminar
Herausgegeben:Specker, E.; Strassen, V.

• Broschiertes Buch

Produktdetails

• Lecture Notes in Computer Science 43
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-540-07805-0
• 1976.
• Seitenzahl: 224
• Erscheinungstermin: 1. Juli 1976
• Deutsch
• Abmessung: 235mm x 155mm x 13mm
• Gewicht: 322g
• ISBN-13: 9783540078050
• ISBN-10: 3540078053
• Artikelnr.: 23117525

Inhaltsangabe

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.