ALGORITHMIC COMPLEXITY OF COMPUTATIONAL PROBLEMS

摘要

Efficiency of computation is mathematically modeled by complexity measures. It is possible to measure complexity of separate computations or complexity of solving a given problem with predetermined computing means. Kolmogorov complexity (also called algorithmic complexity) is one of the most important and popular complexity measures. It studies complexity of solving a specific problem of computing (building) a given word x using recursive algorithms, such as Turing machines. In this paper, we define and study algorithmic complexity for arbitrary computational problems. Computing or building a word is only a very special case of such problems. Algorithmic complexity of computational problems for infinite objects, such as functions, is studied and optimal complexity measures are constructed. In addition, we do not restrict our means of computing to recursive algorithms but also study complexity of solving problems with super-recursive algorithms, such as inductive Turing machines. It has been proved that inductive Turing machines can solve much more problems than Turing machines. It is demonstrated how a hierarchy of inductive Turing machines generates an inductive hierarchy of computational/algorithmic problems. Complexity of computational problems, such as the halting problem for Turing machines, is measured by the classes of automata that are necessary to solve this problem. This theory is aimed at determination of computer abilities in solving different problems and estimation of resources that computers need to do this.