50 years Univerity of Lübeck

Prof. Dr. math. K. Rüdiger Reischuk

Bookcontent


K. Rüdiger Reischuk

Komplexitätstheorie, Band I: Grundlagen:

Maschinenmodelle, Zeit- und Platzkomplexität

Teubner Verlag Stuttgart, 1999

ISBN 3-519-12275-8
DM 59,80


Vorwort V
Inhaltsverzeichnis VII
Abbildungsverzeichnis XI
Tabellenverzeichnis XIII
Einleitung XV
  • 1 Das TM-Modell 1
    • 1.0 Vorbemerkungen 1
    • 1.0.1 Mengen 1
    • 1.0.2 Graphen 2
    • 1.0.3 Strings, Sprachen 4
    • 1.1 Turing-Maschinen 4
    • 1.1.1 Das allgemeine Modell 5
    • 1.1.2 Verschiedene Speichertypen 9
    • 1.1.3 Beispiele für die Arbeitsweise von TM 11
    • 1.1.4 Berechenbarkeit 15
    • 1.1.5 Nichtdeterministische Berechnungen 18
    • 1.2 Das Rechnen mit TM 21
    • 1.2.1 Elementare Techniken 21
    • 1.2.2 Simulation, Band- und Kopf-Reduktion 26
    • 1.2.3 Universelle Maschinen 28
    • 1.3 Mathematische Grundlagen 30
    • 1.3.1 Notation 30
    • 1.3.2 Asymptotisches Wachstum 33
    • 1.3.3 Wachstumsordnungen 37
    • 1.3.4 Rekursionsgleichungen 40
    • 1.4 Die Komplexität von TM 45
    • 1.4.1 Schranken, Masse und Konstruierbarkeit 45
    • 1.4.2 Komplexitätsklassen 49
    • 1.4.3 Diagonalisierung 51
    • 1.4.4 Bandkompression 53
    • 1.4.5 Lineare Beschleunigung 55
    • 1.5 Übungsaufgaben 60
    • 1.6 Bemerkungen und Literatur 66
  • 2 Weitere Maschinenmodelle 69
    • 2.1 Registermaschinen 69
    • 2.1.1 Das RAM-Modell 70
    • 2.1.2 Komplexitätsmasse für RAMs 73
    • 2.1.3 Simulation von RAMs durch TM 76
    • 2.1.4 Simulation von TM durch RAMs 79
    • 2.2 Schaltkreis-Familien 87
    • 2.2.1 Boolesche Funktionen und Schaltkreise 87
    • 2.2.2 Schaltkreiskomplexität 89
    • 2.2.3 Uniformität 94
    • 2.2.4 Simulation von Schaltkreisfamilien durch TM 96
    • 2.2.5 Simulation von TM durch Schaltkreisfamilien 101
    • 2.2.6 Universelle Schaltkreise 109
    • 2.3 Arithmetische Modelle, Entscheidungsgraphen 114
    • 2.3.1 Arithmetische RAMs und Schaltkreise 114
    • 2.3.2 Entscheidungsbaum-Modelle 116
    • 2.4 Übungsaufgaben 118
    • 2.5 Bemerkungen und Literaturhinweise 123
  • 3 Hierarchie-Sätze 129
    • 3.1 Untere Schranken und Komplexitätslücken 129
    • 3.1.1 Logarithmische Platzschranke 130
    • 3.1.2 Quadratische Zeitschranke für 1-Band Maschinen 132
    • 3.1.3 Komplexitätslücke bei zeitbeschränkten 1-Band TM 135
    • 3.1.4 Komplexitätslücke bei kleinen Platzschranken 137
    • 3.2 Deterministische Hierarchien 140
    • 3.2.1 Allgemeiner Hierarchiesatz 140
    • 3.2.2 Zeithierarchien 142
    • 3.2.3 Platzhierarchien 147
    • 3.3 Translation 150
    • 3.4 Nichtdeterministische Hierarchien 154
    • 3.4.1 Abschluss von nichtdeterministischem Platz gegenüber Komplement 154
    • 3.4.2 Nichtdeterministischer Platzhierarchiesatz 158
    • 3.4.3 Nichtdeterministischer Zeithierarchiesatz 160
    • 3.5 Das Komplexitätsmass Reversal 160
    • 3.5.1 Reversalbeschränkte TM 160
    • 3.5.2 Vergleich von Time und Reversal 161
    • 3.5.3 Vergleich von Space und Reversal 163
    • 3.5.4 Bandreduktion und Reversal für NTM 167
    • class="unterkapitel"3.6 Abstrakte Komplexitätstheorie 168
    • 3.6.1 Allgemeines Gap-Theorem 168
    • 3.6.2 Speedup-Theorem 170
    • 3.6.3 Union-Theorem 172
    • 3.6.4 Abstrakte Komplexitätsmasse 174
    • 3.7 Übungsaufgaben 175
    • 3.8 Bemerkungen und Literaturhinweise 180
  • 4 Vergleich von Speicherstrukturen 183
    • 4.1 Ein allgemeines Speichermodell 184
    • 4.1.1 On-line versus off-line 184
    • 4.1.2 Konstruierbare Speicher 185
    • 4.1.3 Lineare Bandsimulation konstruierbarer Speicher 188
    • 4.2  1-dimensionale Speicher 189
    • 4.2.1 Bandreduktion für NTM 189
    • 4.2.2 Simulation von Mehrkopf-Maschinen 191
    • 4.2.3 TM mit separatem Einweg-Eingabeband 192
    • 4.2.4 1 versus 2 Bänder bei Zweiweg-Eingabe 193
    • 4.3 Untere Schranken für Speicherzugriffe 195
    • 4.3.1 Kolmogorov-Komplexität von Strings 195
    • 4.3.2 Der Einfluss des Radius 196
    • 4.4 Obere Schranken für Speicherzugriffe 200
    • 4.4.1 Einbettung von Graphen 200
    • 4.4.2 Kompaktifizierung 205
    • 4.4.3 Schnelle Simulationen 208
    • 4.5 Übungsaufgaben 211
    • 4.6 Bemerkungen und Literatur 213
  • 5 Zeit- versus Platzkomplexität 217
    • 5.1 Time-Space-Relationen für 1-Band TM 218
    • 5.1.1 Simulation platzbeschränkter 1-Band DTM 218
    • 5.1.2 Simulation platzbeschränkter 1-Band NTM 222
    • 5.1.3 Mehrdimensionale 1-Band TM 228
    • 5.2 Das Pebble-Game 229
    • 5.2.1 Berechnungsgraphen 229
    • 5.2.2 Superkonzentratoren 234
    • 5.2.3 Schichtungen von Graphen 237
    • 5.3 Platzeffiziente Simulation von TM und RAMs 246
    • 5.3.1 Lineare Speicher 246
    • 5.3.2 Nichtlineare Speicher 248
    • 5.3.3 Auxiliary Pushdown TM 258
    • 5.4 Simultane Ressource-Schranken 260
    • 5.4.1 Schaltkreisweite 260
    • 5.4.2 Vergleich der Ressourcen von TM und Schaltkreisen 262
    • 5.5 Übungsaufgaben 266
    • 5.6 Bemerkungen und Literaturhinweise 270
  • 6 Sequentielle Komplexitätsklassen 275
    • 6.1 Einführung 275
    • 6.1.1 Notation 276
    • 6.1.2 Zeit-Platz-Hierarchie 277
    • 6.1.3 Reduzierbarkeit, Vollständigkeit 279
    • 6.2 Die Klassen von L bis P 285
    • 6.2.1 Labyrinthprobleme zur Charakterisierung von L und NL 285
    • 6.2.2 P-vollständige Probleme 287
    • 6.3 NP-vollständige Probleme 291
    • 6.3.1 Das Erfüllbarkeitsproblem 291
    • 6.3.2 Selbstreduzierbarkeit 294
    • 6.3.3 Erfüllbarkeit für 3-CNF 296
    • 6.3.4 Graphenprobleme: Cliquen, Kreise und \Überdeckungen 298
    • 6.3.5 Das F\ärbungsproblem für Graphen 302
    • 6.3.6 Diskrete Optimierung 304
    • 6.3.7 NP-Vollständigkeit im strengen Sinne 305
    • 6.3.8 Obere Schranken und Parameterkomplexität 307
    • 6.4 Von NP bis PSPACE 310
    • 6.4.1 Die Struktur von NP 311
    • 6.4.2 Die Relation zwischen NP und co-NP 312
    • 6.4.3 UP, Einweg-Funktionen und Crytologie 316
    • 6.4.4 PSPACE-Vollständigkeit 318
    • 6.5 Linguistische Klassifikationen 321
    • 6.5.1 Formale Grammatiken 321
    • 6.5.2 Die Chomsky-Hierarchie 322
    • 6.5.3 Kontextfreie Sprachen und LogCFL 324
    • 6.5.4 Reguläre Ausdrücke 325
    • 6.6 Übungsaufgaben 327
    • 6.7 Bemerkungen und Literaturhinweise 331
Stichwortverzeichnis 341
Symbolverzeichnis 350
Zeitschriftenverzeicnis 353
Konferenzverzeichnis 354
Verzeichnis von Fachorganisationen 354

Updates: findet man hier