Abstract

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.
I. Kramosil
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.
Kybernetika
D. Seese
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.
Biometrical Journal
K. Zimmerman
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.
Optimization