Calude C. Theories of Computational Complexity

Издательство North-Holland, 1988, -500 pp.During the 1890's, when Peano's five axioms were set afloat, a great effort was done to establish what functions are or are not what we can today algorithmically computable functions. Dedekind and Peano have been the first to use functions defined by induction, an important preliminary stage of the recursive function theory. The foundational problem, arising from Cantor's development of the set theory have led to an increasing interest in the two millenia old intuitive notion of algorithm. Some forms close to the modern use of algorithms can be found in the works written in the rust quarter of the 20th century by Borel and Weyl. Around 1930's, Godel, Church, Kleene and Turing have provided different, but equivalent, formalisms for characterising the number-theoretic functions computable by algorithms, i.e. the algorithmically computable (effectively calculable) functions.
The deep understanding of algorithmic computability as well as the spectacular growth of computer technology gave rise to a new, large and active field which basically refers to the question "how difficult to compute is a given algorithmically computable function"; this question was rust explicitly posed by Rabin in 1959-1960.
The computational complexity studies fall into a variety of directions, some of which are now available in monographs (Aho, Hopcroft and Ullman [1974], for the complexity of specific functions, Borodin and Munro [1975], for algebraic complexity, Garey and Johnson [1978], for NP-complete problems), or in section. of some books on computation theory (see, for example, Brainerd and Landweber [1974], or Machtey and Young [1978]). A thorough going look into the field is provided by the overviews or Hartmanis and Hopcroft [1971], Rabin [1977] and Cook [1983].
Our attempt is not to give a comprehensive description or the field, but rather to present, in a rigorous and unitary form, four machine-independent theories of computational complexity, whose selection is motivated by their intrinsic importance and practical relevance. One or them (i.e. the Kolmogorov and Martin-Lof theory) was never synthesised in a separate monograph or as chapter or one. The otherse are presented sometimes, but in a very telegraphic form. The book includes a wealth or results, classical, new and others which have not been published before. In developing the mathematic. underlying the size, dynamic and structural complexity measures, various connexions with mathematical logic, constructive topology, probability and programming theories are established.
The book is organised in five chapters. The first chapter is devoted to a complexity-theoretic analysis of the class of primitive recursive functions, along the way initiated by Grzegorczyk. We are dealing with hierarchies of primitive recursive functions built, on the rate of growth, by algebraic methods. Chapter 2 is a self-contained and complexity-oriented presentation of the basic recursive function theory. Chapter 3 presents the BLUM abstract theory of computational complexity. It contains a detailed algebraic and topological study of dynamic complexity measures. Chapter 4 is dealing with the Kolmogorov and Martin-Lof theory of complexity. This theory, referring to the complexity of "algorithmic descriptions", is developed within a non-binary framework. It allows a satisfactory definition of "random strings", which turns out to have many interesting applications. The last chapter goes into the direction initiated, among others, by Meyer and Ritchie; it contains an analysis of some subrecursive hierarchies built on the restricted use of a few natural programming scheme. In this more intuitive chapter we make use of all type of complexity measures, previously discussed.
Prior to 1930 mathematicians were able to prove the algorithmic computability of some particular functions; but, the lack of a general representation of algorithmic computability made impossible the detection of non-computable Functions. The mid 60's marked a similar situations. concerns the difficulty of computations. Hence, most of results are negative. But, as Machtey and Young said at the beginning of Chapter 5 or their book, "these results point the way to, and underscore the necessity for, developing approaches to programming which overcome the,se limitations",
We have tried to present facts in detail. Extensive examples are included, to motivate and clarify notions and constructions. The lists of exercises and problems contain routine exercises, further interesting results, as well as some open problems.
The book is primarily written for mathematicians and computer scientists; it may be of interest to logicians and philosophers.Primitive Recursh'e Hierarchie
Recursive Functions
Blum's, Complexity Theory
Kolmogorov and Martin-Lof's Complexity Theory
Subrecursive Programming Hierarchies