1 Intro duction
The sub ject of complexity theory
The need to be able to measure the complexityof a
problem, algorithm or structure, and to obtain bounds and quantitive relations for complexity
arises in more and more sciences: besides computer science, the traditional branches of
mathematics, statistical physics, biology, medicine, social sciences and engineering are also
confronted more and more frequently with this problem. In the approachtaken by computer
science, complexity is measured by the quantity of computational resources (time, storage,
program, communication). These notes deal with the foundations of this theory.
Computation theory can basically be divided into three parts of dierentcharacter. First,
the exact notions of algorithm, time, storage capacity, etc. must be introduced. For this,
dierent mathematical machine models must b e dened, and the time and storage needs
of the computations p erformed on these need to be claried (this is generally measured as
a function of the size of input). By limiting the available resources, the range of solvable
problems gets narrower this is howwe arrive at dierent complexity classes. The most
fundamental complexity classes provide important classication even for the problems arising
in classical areas of mathematics this classication reects well the practical and theoretical
diculty of problems. The relation of dierent machine mo dels to each other also belongs
to this rst part of computation theory.
Second, one must determine the resource need of the most imp ortant algorithms in various
areas of mathematics, and give ecient algorithms to prove that certain imp ortant problems
belong to certain complexity classes. In these notes, we do not strive for completeness in the
investigation of concrete algorithms and problems this is the task of the corresp onding elds
of mathematics (combinatorics, operations research, numerical analysis, number theory).
Third, one must nd metho ds to prov
e \negative results",
i.e.
for the pro of that some
problems are actually unsolvable under certain resource restrictions. Often, these questions
can be formulated by asking whether some introduced complexity classes are dierentor
empty. This problem area includes the question whether a problem is algorithmically solvable
at all this question can today b e considered classical, and there are many imp ortant results
related to it. The ma jority of algorithmic problems o ccurring in practice is, however, such
that algorithmic solvability itself is not in question, the question is only what resources must
be used for the solution. Suchinvestigations, addressed to lower bounds, are very dicult
and are still in their infancy. In these notes, we can only give a taste of this sort of result.
It is, nally,worth remarking that if a problem turns out to have only \dicult" solutions,
this is not necessarily a negative result. More and more areas (random number generation,
communication protocols, secret communication, data protection) need problems and struc-
tures that are guaranteed to b e complex. These are imp ortant areas for the application of
complexity theory from among them, we will deal with cryptography, the theory of secret
communication.
Some notation and denitions
A nite set of symbols will sometimes be called an
alphabet
. A nite sequence formed from some elements of an alphabet is called a
word
.
The emptyword will also be considered a word, and will b e denoted by
. The set of words
of length
n
over is denoted by
n
, the set of all words (including the emptyword) over
is denoted by
. A subset of
,
i.e.
, an arbitrary set of words, is called a
language
.
4
评论0