The algorithmic solvability of some problems can be very far from their practical solvability. There are algorithmically solvable problems that cannot be solved, for an input of a given size, in fewer than exponentially or doubly exponentially many steps (see Chapter 4). Complexity theory, a major branch of the theory of algorithms, investigates the solvability of individual problems under certain resource restrictions. The most important resources are time and space (storage).
We define these notions in terms of the Turing machine model of computation. This definition is suitable for theoretical study; in describing algorithms, using the RAM is more convenient, and it also approximates reality better. It follows, however, from our constructions in section 1.3 that from the point of view of the most important complexity classes (e.g. polynomial time and space) it does not matter, which one is used in the definition.
This leads os to the definition of various complexity classes: classes of problems solvable within given time bounds, depending on the size of the input. Every positive function of the input size defines such a class, but some of them are particularly important. The most central complexity class is polynomial time. Many algorithms important in practice run in polynomial time (in short, are polynomial). Polynomial algorithms are often very interesting mathematically, since they are built on deeper insight into the mathematical structure of the problems, and often use strong mathematical tools.
We restrict the computational tasks to yes-or-no problems; this is too much of a restriction, and pays off in what we gain simplicity of presentation. Note that the task of computing any output can be broken down to computing its bits in any reasonable binary representation.
Most of this chapter is spent on illustrating how certain computational tasks can be solved within given resource contraints. We start with the most important case, and show that most of the basic everyday computational tasks can be solved in HREF="http:poly.ps"> polynomial time polynomial time.
First, we show that a large number of basic tasks in Then we describe several algorithms in graph theory. Here we
cannot in any sense survey all the basic graph algorithms; we'll
restrict ourselves to a few that will be needed later.
Polynomial space is a much more
general class (i.e., a much less restrictive resource constraint. The
most important computational problems solvable in polynomail space
(but most probably not in polynomial time) are {\it games} like chess
or GO. We give a detailed description of this connection.
We end with a briefer discussion of other typical complexity classes.
1. The distinguished role of polynomial algorithms is underscored by
the fact that some natural syntactic conditions can be imposed on an
algorithm that are equivalent to requiring that it runs in polynomial
time.
If we restrict, say, the programming language Pascal, by forbidding
function calls, as well as the statements ``goto'',
``repeat'' or ``while'', and we require that the upper bound of
the ``for'' instructions is the size of the input, then all
algorithms that we program are automatically polynomial. The converse
is also true: all polynomial algorithms can be programmed this way.
2. Let us recall the Church Thesis: all functions computable in
some intuitive sense are computable on the Turing machine. Church
stated this thesis around 1931.
Later, it became apparent that not only can all imaginable machine
models simulate each other but the ``reasonable'' ones can simulate
each other in {\em polynomial time}. This is the Polynomial Church's
Thesis (so called, probably, by L. Levin); here is a more detailed
explanation of its meaning. We say that machine B simulates
machine A in polynomial time if there is a constant k
such that for any positive integer t and any input, t
steps of the computation of machine A will be simulated by a
number of steps of machine B that is polynomial in t.
By ``reasonable'', we mean the following two requirements:
--- Not unnaturally restricted in its operation.
--- Not too far from physical realizability.
The first requirement excludes models like an automaton enhanced with
two counters; though some such machines may be able to compute all
computable functions, but often only very slowly.\footnote{Such machines are
of undeniable theoretical interest. Indeed, when we want to reduce an
undecidability result concerning computers to an undecidability result
concerning, say, sets of integer equations, it is to our advantage to
use as simple a model of a computer as possible. But when our concern
is the complexity of computations, such models can be excluded.}
All machine models we considered so far are rather reasonable, and
all simulations considered so far were done in polynomial time.
A machine that does not satisfy the second requirement is a
cellular automaton where the cells are arranged on an infinite binary
tree. Such a machine (or other, similar machines called PRAM and
considered later in these notes) could mobilize, in a given number of
steps, the computing power of an exponential number of processors to
the solution of some problems. But so many processors would simply
not fit into our physical space.
Recently, quantum computers have been introduced (so far, only on
paper), that do not seem to obey the Polynomial Church Thesis. For
example, quantum computers can factor an integer into primes in
polynomial time, which is supposed to be impossible using a Turing
machine. But it is not clear whether the real-life realization of such
machines contradicts any physical law; on the other hand, it is
possible that these tasks (like factoring an integer) can be also
solved by a Turing machine in polynomail time, just in a more
sophisticated way.
The main consequence of the Polynomial Church's Thesis is that one
can simply speak of functions computable in polynomial time (these
are sometimes called ``feasible'') without referring to the machine
on which they are computable, as long as the machine is
``reasonable''. This certainly is true for the machine models
we introduced in Chapter 1.
General remarks on polynomial time