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.

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 |