Komplexität von Entscheidungsproblemen Ein Seminar

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.

Dettagli sul prodotto

• Con la collaborazione di: V. Strassen (Editore), E. Specker (Editore), Strassen (Editore), E Specker (Editore), Specker (Editore), Strassen (Editore)
• Editore: Springer, Berlin
• Contenuto: Libro
• Forma del prodotto: Tascabile
• Data pubblicazione: 29.06.2009
• Categoria: Scienze naturali, medicina, informatica, tecnica > Informatica, EDP > Informatica
• EAN: 9783540078050
• ISBN: 978-3-540-07805-0
• Illustrazioni: 217 S.
• Altezza (della confezione): 23.5 cm
• Peso (della confezione): 322 g
• Serie: Lecture Notes in Computer Science > Bd.43; Lecture Notes in Computer Science > 43
• Categorie: Entscheidung, Algorithmen, Komplexitätstheorie, Komplexität, aussagenlogik, Komplexität(Kybern.), Entscheidung(Math.)