Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter

Название: Theories of Computational Complexity

Автор: Calude C.

Аннотация:

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.