Theories of Computational Complexity: Volume 35
Published on 1. January 1988
Book
Hardback
486 pages
978-0-444-70356-9 (ISBN)
Description
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.
Reviews / Votes
I. KramosilThe book meets the traditional high level of North-Holland mathematical monographs and can be recommended to postgraduate students beginning their studies in the domain of theoretical computer science and theory of recursive functions, as well as to specialists from other fields of pure and applied mathematics.KybernetikaD. SeeseThe monograph contains a wealth of results, classical and new ones. Many exercises and examples are provided to test and improve the readers understanding. The monograph is an interesting contribution to the area of complexity theory which can be recommended for research and graduate students in computer science, mathematical logic and discrete mathematics as a text or reference book.Biometrical JournalK. ZimmermanThe book fills a gap existing up to now in the literature concerning the complexity theory, since it presents in a rigorous and unitary form complexity theories, which either has not yet been presented in a monographic form, or were presented in a very shortened way. The book will be of interest both for mathematicians and for computer scientists.OptimizationMore details
Series
Language
English
Place of publication
United States
Publishing group
Elsevier Science & Technology
Target group
Professional and scholarly
ISBN-13
978-0-444-70356-9 (9780444703569)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Calude | C. Calude
Theories of Computational Complexity
E-Book
05/2014
North-Holland
€112.00
Available for download
Content
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.