Theories of computational complexity (Q1210716)

This book represents wide areas of abstract complexity theory, or rather `theories' as the title suggests. The areas discussed in the book, each of them representing another concept of complexity, are the following ones: Subrecursive hierarchies, Blum's complexity theory, Kolmogorov's complexity theory and Martin-Löf's complexity theory. Not contained are the NP-problem, time and space hierarchies for Turing machines and the complexity of theories. The material is presented at a high level and contains many results of recent research (partly from the author himself). The point of view of the presentation is rather a mathematical than a computational one (no machine models for computation). Subrecursive hierarchies are defined by Ackermann's function as well as by (the less known) Sudan's function. The approach is similar but not identical to Grzegorczyk's one, because the classes are defined to be closed under limited iteration (instead of limited primitive recursion). The section also contains a discussion of primitive recursive string functions. The class of recursive functions is defined in the usual way (basic functions and operations) as well as by definition schemes in the spirit of Kleene's original approach; both concepts are shown to be identical. Gödel numberings are introduced and classical results as the recursion theorem and Rice's theorem are proved. The halting problem and other undecidable problems are discussed, as well as recursive operator theory and recursive real numbers. It follows a detailed discussion of Blum's complexity theory including the gap-, honesty- and speed-up theorem. While Blum's theory is even linked to topological analysis, one misses some concrete interpretations in terms of computer science. So there are no machine models of computation or models of algorithms as the \(\lambda\)-calculus, which could be used to illustrate the importance of the results; the LOOP- language for the primitive recursive functions is introduced not earlier than in the last chapter. The chapter on Kolmogorov's and Martin-Löf's complexity concepts is very interesting and contains a considerable wealth of results; there is even a link to Gödel's first incompleteness theorem. The last chapter deals with the LOOP-hierarchy. Unfortunately, the computing time of a program is defined verbally only, but not formally (an unpleasant feature which can also be found in other books); a definition of an interpreter for the LOOP-language would be necessary in order to close this gap. It is shown, that Sudan's hierarchy and the LOOP-hierarchy are identical. Some interesting results of Machtey and Young on program size are added. The book contains an impressing wealth of results, which never before were presented under a common point of view. With the exception of NP- completeness and complexity of theories, the mathematical side of complexity is very well represented. On the other hand, there would be ways to make the book more attractive for computer scientists. The representation of Ackermann's function in a FORTRAN code shows some art of programming but does not reflect the use of modern computational concepts (as recursion). The informal definition of computing time could be replaced by a formal one. As a minor detail, Gödel and Martin-Löf should not be written as `Godel' and `Martin-Lof'.