Theories of Computational Complexity - 1st Edition - ISBN: 9780444703569, 9780080867755

Theories of Computational Complexity, Volume 35

1st Edition

Authors: C. Calude
eBook ISBN: 9780080867755
Imprint: North Holland
Published Date: 1st January 1988
Page Count: 486
Tax/VAT will be calculated at check-out Price includes VAT (GST)
112.00
90.00
148.00
Unavailable
Price includes VAT (GST)
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents

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.


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.


Details

No. of pages:
486
Language:
English
Copyright:
© North Holland 1988
Published:
Imprint:
North Holland
eBook ISBN:
9780080867755

Reviews

@from:I. Kramosil @qu:The 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. @source:Kybernetika @from:D. Seese @qu:The 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. @source:Biometrical Journal @from:K. Zimmerman @qu:The 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. @source:Optimization


About the Authors

C. Calude Author