Theories of Computational Complexity (eBook)
486 Seiten
Elsevier Science (Verlag)
978-0-08-086775-5 (ISBN)
In developing the mathematics underlying the size, dynamic and structural complexity measures, various connections with mathematical logic, constructive topology, probability and programming theories are established. The facts are presented in detail. Extensive examples are provided, to help clarify notions and constructions. The lists of exercises and problems include routine exercises, interesting results, as well as some open problems.
This volume presents four machine-independent theories of computational complexity, which have been chosen for their intrinsic importance and practical relevance. The book includes a wealth of results - classical, recent, and others which have not been published before.In developing the mathematics underlying the size, dynamic and structural complexity measures, various connections with mathematical logic, constructive topology, probability and programming theories are established. The facts are presented in detail. Extensive examples are provided, to help clarify notions and constructions. The lists of exercises and problems include routine exercises, interesting results, as well as some open problems.
Front Cover 1
Theories of Computational Complexity 4
Copyright Page 5
Contents 12
Preface 8
Introduction 14
Chapter 1 16
1. Primitive Recursive Hierarchies 16
1.1. Examples 16
1.2. Ackermann-Peter's Hierarchy 20
1.3. Primitive Recursive Functions 35
1.4. Primitive Recursive Invariants 39
1.5. Primitive Recursive Enumerations 45
1.6. Sudan's Hierarchy 58
1.7. Universal Sequences of Primitive Recursive Functions 75
1.8. Primitive Recursive String-functions 84
1.9. History 90
1.10. Exercises and Problem 92
Chapter 2 100
2. Recursive Functions 100
2.1. Examples 100
2.2. Arithmetization of Computation: An Example 105
2.3. Equational Characterization of Partial Recursive Functions 112
2.4. GODEL Numberings 142
2.5. Recursively Enumerable Sets 157
2.6. Undecidability and Independence 172
2.7. Uniformity 184
2.8. Operators 191
2.9. Recursive Real Numbers 208
2.10. History 214
2.11. Exercises and Problems 216
Chapter 3 220
3. BLUM’s Complexity Theory 220
3.1. Examples 220
3.2. BLUM Spaces 224
3.3. Recursive Dependence of Complexity Measures 231
3.4. Complexity Classes 239
3.5. The Speed-up Phenomenon 262
3.6. The Union Theorem 276
3.7. Hard Recursive Functions 281
3.8. Complexity Sequences 286
3.9. A Topological Analysis 291
3.10. History 305
3.11. Exercises and Problems 307
Chapter 4 310
4. KOLMOGOROV and MARTIN-LOF’s Complexity Theory 310
4.1. Examples 310
4.2. KOLMOGOROV’s Complexity 316
4.3. MARTIN-LOF Tests 326
4.4. Undecidability Theorems 343
4.5. Representability Theorems 353
4.6. Recursive MARTIN-LOF Tests 365
4.7. Infinite Oscillations 374
4.8. Probabilistic Algorithms 381
4.9. History 389
4.10. Exercises and Problems 390
Chapter 5 396
5. Subrecursive Programming Hierarchies 396
5.1. Examples 396
5.2. The LOOP Language 397
5.3. LOOP Hierarchies 404
5.4. A Universal Language 415
5.5. A Dynamic Characterization of LOOP Classes 420
5.6. Augmented LOOP Languages 429
5.7. Simple Functions 440
5.8. Program Size 453
5.9. History 459
5.10. Exercises and Problems 460
Bibliography 466
Index of notations 482
Subject index 488
Author index 494
| Erscheint lt. Verlag | 18.8.2011 |
|---|---|
| Sprache | englisch |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Mathematik / Informatik ► Mathematik ► Angewandte Mathematik | |
| Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik | |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| Naturwissenschaften | |
| Technik | |
| ISBN-10 | 0-08-086775-8 / 0080867758 |
| ISBN-13 | 978-0-08-086775-5 / 9780080867755 |
| Haben Sie eine Frage zum Produkt? |
PDF (Adobe DRM)Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
