Complexity of Algorithms Lctn - Peter Gacs.pdf

(811 KB) Pobierz
MAIN
Complexity of Algorithms
Lecture Notes, Spring 1999
Peter Gacs
Boston University
and
Laszl´oLovasz
Yale University
1
Contents
0 Introduction and Preliminaries 1
0.1 The subject of complexity theory ........................... 1
0.2 Some notation and definitions ............................. 2
1 Models of Computation 3
1.1 Introduction ....................................... 3
1.2 Finite automata .................................... 5
1.3 The Turing machine .................................. 8
1.4 The Random Access Machine ............................. 18
1.5 Boolean functions and Boolean circuits ........................ 24
2 Algorithmic decidability 31
2.1 Introduction ....................................... 31
2.2 Recursive and recursively enumerable languages ................... 33
2.3 Other undecidable problems .............................. 37
2.4 Computability in logic ................................. 42
3 Computation with resource bounds 50
3.1 Introduction ....................................... 50
3.2 Time and space ..................................... 50
3.3 Polynomial time I: Algorithms in arithmetic ..................... 52
3.4 Polynomial time II: Graph algorithms ........................ 57
3.5 Polynomial space .................................... 62
4 General theorems on space and time complexity 65
4.1 Space versus time .................................... 71
5 Non-deterministic algorithms 72
5.1 Non-deterministic Turing machines .......................... 72
5.2 Witnesses and the complexity of non-deterministic algorithms ........... 74
5.3 General results on nondeterministic complexity classes ............... 76
5.4 Examples of languages in NP ............................. 79
5.5 NP-completeness .................................... 85
5.6 Further NP-complete problems ............................ 89
6 Randomized algorithms 99
6.1 Introduction ....................................... 99
6.2 Verifying a polynomial identity ............................ 99
6.3 Prime testing ......................................103
6.4 Randomized complexity classes ............................108
2
7 Information complexity: the complexity-theoretic notion of randomness 112
7.1 Introduction .......................................112
7.2 Information complexity ................................112
7.3 The notion of a random sequence ...........................117
7.4 Kolmogorov complexity and data compression ....................119
8 Pseudo-random numbers 124
8.1 Introduction ......................................124
8.2 Introduction ......................................124
8.3 Classical methods ....................................125
8.4 The notion of a psuedorandom number generator ..................127
8.5 One-way functions ...................................130
8.6 Discrete square roots ..................................133
9 Parallel algorithms 135
9.1 Parallel random access machines ...........................135
9.2 The class NC ......................................138
10 Decision trees 143
10.1 Algorithms using decision trees ............................143
10.2 The notion of decision trees ..............................146
10.3 Nondeterministic decision trees ............................147
10.4 Lower bounds on the depth of decision trees .....................151
11 Communication complexity 155
11.1 Communication matrix and protocol-tree ......................155
11.2 Some protocols .....................................159
11.3 Non-deterministic communication complexity ....................160
11.4 Randomized protocols .................................164
12 The complexity of algebraic computations
166
13 Circuit complexity 167
13.1 Introduction .......................................167
13.2 Lower bound for the Majority Function .......................168
13.3 Monotone circuits ...................................170
14 An application of complexity: cryptography 172
14.1 A classical problem ...................................172
14.2 A simple complexity-theoretic model .........................172
14.3 Public-key cryptography ................................173
14.4 The Rivest-Shamir-Adleman code ...........................175
0
0 Introduction and Preliminaries
0.1 The subject of complexity theory
The need to be able to measure the complexity of 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 approach taken by computer science, complexity is measured by the quantity
of computational resources (time, storage, program, communication) used up by a particualr
task. These notes deal with the foundations of this theory.
Computation theory can basically be divided into three parts of different character. First,
the exact notions of algorithm, time, storage capacity, etc. must be introduced. For this, dif-
ferent mathematical machine models must be defined, and the time and storage needs of the
computations performed on these need to be clarified (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 how we arrive at different complexity classes. The most fundamental com-
plexity classes provide an important classification of problems arising in practice, but (perhaps
more surprisingly) even for those arising in classical areas of mathematics; this classification
reflects the practical and theoretical diculty of problems quite well. The relationship between
different machine models also belongs to this first part of computation theory.
Second, one must determine the resource need of the most important algorithms in various
areas of mathematics, and give ecient algorithms to prove that certain important 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 corresponding
fields of mathematics (combinatorics, operations research, numerical analysis, number theory).
Nevertheless, a large number of concrete algorithms will be described and analyzed to illustrate
certain notions and methods, and to establish the complexity of certain problems.
Third, one must find methods to prove “negative results”, i.e. for the proof that some
problems are actually unsolvable under certain resource restrictions. Often, these questions can
be formulated by asking whether certain complexity classes are different or empty. This problem
area includes the question whether a problem is algorithmically solvable at all; this question can
today be considered classical, and there are many important results concerining it; in particular,
the decidability or undecidablity of most concrete problems of interest is known.
The majority of algorithmic problems occurring 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. Such investigations, 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 results. In particular, we
discuss complexity notions like communication complexity or decision tree complexity, where
by focusing only on one type of rather special resource, we can give a more complete analysis
of basic complexity classes.
It is, finally, worth noting that if a problem turns out to be “dicult” to solve, this is not
necessarily a negative result. More and more areas (random number generation, communication
protocols, cryptography, data protection) need problems and structures that are guaranteed to
1
be complex. These are important areas for the application of complexity theory; from among
them, we will deal with random number generation and cryptography, the theory of secret
communication.
0.2 Some notation and definitions
. The set of words of length n over Σ is denoted by Σ n , the set of all
words (including the empty word) over Σ is denoted by Σ ∗ . A subset of Σ ∗ , i.e. , an arbitrary
set of words, is called a language .
Note that the empty language is also denoted by
∅
∅
but it is different, from the language
{∅}
containing only the empty word.
Let us define some orderings of the set of words. Suppose that an ordering of the elements
of Σ is given. In the lexicographic ordering of the elements of Σ ∗ , a word α precedes a word β if
either α is a prefix (beginning segment) of β or the first letter which is different in the two words
is smaller in α . (E.g., 35244 precedes 35344 which precedes 353447.) The lexicographic ordering
does not order all words in a single sequence: for example, every word beginning with 0 precedes
the word 1 over the alphabet
{
0 , 1
}
{
0 , 1
} ∗ we get when we write up the natural numbers in the binary
number system.
The set of real numbers will be denoted by R , the set of integers by Z and the set of rational
numbers (fractions) by Q . The sign of the set of non-negative real (integer, rational) numbers
is R +
( Z + , Q + ). When the base of a logarithm will not be indicated it will be understood to
be 2.
Let f and g be two real (or even complex) functions defined over the natural numbers. We
write
f = O ( g )
if there is a constant c> 0 such that for all n large enough we have
|
f ( n )
|≤
c
|
g ( n )
|
. We write
f = o ( g )
if f is 0 only at a finite number of places and f ( n ) /g ( n )
→
0if n
→∞
. We will also use
sometimes an inverse of the big O notation: we write
f =Ω( g )
if g = O ( f ). The notation
f =Θ( g )
means that both f = O ( g ) and g = O ( f ) hold, i.e. there are constants c 1 ,c 2 > 0 such that
for all n large enough we have c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ). We will also use this notation within
formulas. Thus,
( n +1) 2 = n 2 + O ( n )
2
A finite set of symbols will sometimes be called an alphabet . A finite sequence formed from some
elements of an alphabet Σ is called a word . The empty word will also be considered a word,
and will be denoted by
. The increasing order is therefore often preferred: here,
shorter words precede longer ones and words of the same length are ordered lexicographically.
This is the ordering of

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin