LIMITED OFFER
Save 50% on book bundles
Immediately download your ebook while waiting for your print delivery. No promo code is needed.
Theories of Computational Complexity
- 1st Edition, Volume 35 - January 1, 1988
- Author: C. Calude
- Language: English
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 8 6 7 7 5 - 5
This volume presents four machine-independent theories of computational complexity, which have been chosen for their intrinsic importance and practical relevance. The book includes… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteThis 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.
Primitive Recursive Hierarchies. Examples. Ackermann-Peter's Hierarchy. Primitive Recursive Functions. Primitive Recursive Invariants. Primitive Recursive Enumerations. Sudan's Hierarchy. Universal Sequences of Primitive Recursive Functions. Primitive Recursive String-Functions. History. Exercises and Problems.Recursive Functions. Examples. Arithmetization of Computation: An Example. Equational Characterization of Partial Recursive Functions. Godel Numberings. Recursively Enumerable Sets. Undecidability and Independence. Uniformity. Operators. Recursive Real Numbers. History. Exercises and Problems.Blum's Complexity Theory. Examples. Blum Spaces. Recursive Dependence of Complexity Measures. Complexity Classes. The Speed-Up Phenomenon. The Union Theorem. Hard Recursive Functions. Complexity Sequences. A Topological Analysis. History. Exercises and Problems.Kolmogorov and Martin-Lof's Complexity Theory. Examples. Kolmogorov's Complexity. Martin-Lof Tests. Undecidability Theorems. Representability Theorems. Recursive Martin-Lof Tests. Infinite Oscillations. Probabilistic Algorithms. History. Exercises and Problems.Subrecursive Programming Hierarchies. Examples. The LOOP Language. LOOP Hierarchies. A Universal Language. A Dynamic Characterization of LOOP Classes. Augmented LOOP Languages. Simple Functions. Program Size. History. Exercises and Problems. Bibliography. Indexes.
- No. of pages: 486
- Language: English
- Edition: 1
- Volume: 35
- Published: January 1, 1988
- Imprint: North Holland
- eBook ISBN: 9780080867755
Read Theories of Computational Complexity on ScienceDirect