×

zbMATH — the first resource for mathematics

Computational complexity. (English) Zbl 0584.68062
Mathematiche Monographien, Bd. 19. Berlin: VEB Deutscher Verlag der Wissenschaften, 551 p. (1986).
The book is devoted to computational complexity of the family of all algorithms, not to restricted notions of algorithms such as automata or Boolean networks. The greater part of the book deals with the machine- oriented measures such as time and space measures. The authors try to cover all branches of the theory up to 1984. The book consists of three parts.
In part 1 the basic notions and results of the theory of computational complexity are introduced.
Part 2 studies problems concerning one complexity measure only, in particular, the complexity of single problems, the properties of complexity classes from various points of view (recursion theory, algebra, formal languages, automata, reducibilities) and the properties of complexity measures.
Part 3 deals with the relationship between different measures and relativised computational complexity. In particular, problems of simulations between different types of machines, determinism versus nondeterminism and time versus space are considered. The bibliography contains about of 1000 items.
Contents: Part 1. Basic concepts. 1. Preliminaries, 2. Recursive functions, 3. Reducibility, 4. Formal languages, 5. Measures of computational complexity, 6. Complexity bounded reducibilities; Part 2. Complexity classes and complexity measures. 7. Upper bounds, 8. Lower bounds, 9. Overcoming lower bounds, 10. Complexity classes and recursion, 11. Complexity classes and algebraic operations, 12. Complexity classes and grammars, 13. Complexity classes and automata, 14. Complexity classes and reducibility, 15. General properties of complexity measures, 16. Properties of specific measures, 17. Hierarchies, 18. Speed-up; Part 3. Relationships between different measures. 19. Realistic space and time measure, 20. Further time and space measures, 21. Further measures, 22. Relationships between specific complexity classes, 23. NSPACE versus DSPACE, 24. NTIME versus DTIME, 25. The space-time problem for machine oriented measures, 26. The general space-time problem, 27. Oracles, 28. Relativization of the D-ND-problems and the space-time problems.
Reviewer: M.Kratko

MSC:
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations