Description
(Table of content)
Inhaltsübersicht.- Erstes Buch: Elementare Berechnungstheorie.- A: Mathematischer Algorithmusbegriff.- B: Komplexität Algorithmischer Unlösbarkeit.- C: Rekursivität und Komplexität.- Zweites Buch: Elementare Prädikatenlogik.- D: Logische Analyse Des Wahrheitsbegriffs.- E: Logische Analyse Des Beweisbegriffs.- F: Komplexität Logischer Entscheidungsprobleme.- Bibliographie.- Symbolverzeichnis.
(Author portrait)
Egon Börger ist Professor für Informatik an der Universität Pisa (Italien) und Alexander-von-Humboldt-Forschungspreisträger.
(Table of content)
hlbare Prädikate Darstellungssätze, Universalität.- 2. Arithmetische Hierarchie Aufzählungs- und Hierarchiesatz Darstellungssatz, Komplexitätsbestimmungen (Unendlichkeits-, Anzahlaussagen, arithmetischer Wahrheitsbegriff).- 3. Reduktionsbegriffe und Unlösbarkeitsgrade Reduktionsbegriffe (Satz von Post), Indexmengen (Satz von Rice & Shapiro, ?n -vollständige Programmeigenschaften), Kreativität und ?1-Vollständigkeit (Satz von Myhill), Einfache Mengen (?1. versus ?m versus ?tt, Satz von Decker und Yates), Prioritätsmethode (Satz von Friedberg & Muchnik), Komplexität des arithmetischen Wahrheitsbegriffs.- III Allgemeine Berechnungskomplexität.- 1. Beschleunigungsphänomen Allg. Komplexitätsmaße, Blumscher Beschleunigungssatz, Unmöglichkeit effektiver Beschleunigung.- 2. Beliebig komplizierte Funktionen Satz von Rabin-Blum-Meyer über Funktionen beliebig großer Programm- oder Rechenzeitkomplexität, Blumscher Programmverkürzungssatz, Lückensatz, Vereinigungssatz.- 3. Zerlrgungstheorie universeller Automaten Charakterisierung der Laufzeit-, Ein-, Ausgabe-, Übergangs- und Stopfunktionen universeller Automaten; Unmöglichkeit uniformer rekursiver Simulationsschranken bei universellen Automaten.- C: Rekursivität und Komplexität.- I Komplexitätsklassen Rekursiver Funktionen.- 0. Das Modell der k-Band-Turingmaschine Bandreduktion, Band- und Zeitkompression, Simulationskomplexität eines universellen Programms.- 1. Zeit- und Platzhierarchiesätze Satz von Fürer.- 2. Komplexität nickt determinierter Programme Satz von savitch.- II Komplexitätsklassen Primitiv Rekursiver Funktionen.- 1. Grzegorczyk-Hierarchiesatz Äquivalenz der Charakterisierungen durch Wachstum (beschränkte Rekursionen, Einsetzungen in Ackermannzweige), Rekursions- und Looptiefe, Rechenzeitkomplexität aus Kleene-Normalform mit polynomialbeschränkten bzw. R3-Kodierungsfunktionen.- 2. En-Basis- und En -Rechenzeithierarchiesatz.- 3. Ackermannfunktion und Goodstein-Folgen Satz von Goodstein & Kirby & Paris.- III Polynomial und Exponentiell Beschränkte Komplexitätsklassen.- 1. NP-vollständige. Probleme. Halte-, Domino-, Partitions-, Rucksack-, Cliguen-, Handlungsreisenden- und ganz-zahliges Programmierungsproblem.- 2. Vollständige Probleme für PBAND und exponentielle Klassen.- IV Endliche Automaten.- 1. Charakterisierungen durch (in-) determinierte Akzeptoren und Akzeptoren und reguläre Ausdrücke Sätze von Rabin & Scott, Kleene.- 2. Charakterisierung durch Kongruenzrelationen der Ununterscheid-barkeit Satz von Myhill & Nerode mit Korollaren (Zustands- minimalisierung, Beispiele nicht regulärer Sprachen, Schleifenlemma, 2-Weg-Automaten).- 3. Zerlegungssätze Produktzerlegung, Modulare Zerlegung (Röddingsche Normalform bei sequentieller und paralleler Signalverarbeitung).- 4. Kleine universelle Programme 2-dimensionale TM mit 2 Zuständen und 4 Buchstaben, 2-dimensionales Thuesystem mit 2 Regeln und 3 Buchstaben, PBAND-Vollständiges Schleifenproblem.-
