Komplexität von Entscheidungsproblemen
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.
| Erscheint lt. Verlag | 1.7.1976 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | 217 S. |
| Verlagsort | Berlin |
| Sprache | deutsch |
| Maße | 155 x 235 mm |
| Gewicht | 322 g |
| Themenwelt | Mathematik / Informatik ► Informatik ► Theorie / Studium |
| Schlagworte | Algorithmen • Aussagenlogik • Entscheidung • Entscheidung (Math.) • Komplexität • Komplexität (Kybern.) • Komplexitätstheorie |
| ISBN-13 | 9783540078050 / 9783540078050 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
