Complexity of algorithms

Introduction......Page 9
Some notation and definitions......Page 10
Models of Computation......Page 13
Finite automata......Page 15
The Turing machine......Page 18
The Random Access Machine......Page 29
Boolean functions and Boolean circuits......Page 35
Algorithmic decidability......Page 45
Recursive and recursively enumerable languages......Page 46
Other undecidable problems......Page 51
Godel's incompleteness theorem......Page 57
First-order logic......Page 60
Computation with resource bounds......Page 67
Polynomial time......Page 70
Other complexity classes......Page 82
General theorems on space and time complexity......Page 85
Non-deterministic algorithms......Page 95
Non-deterministic Turing machines......Page 96
Witnesses and the complexity of non-deterministic algorithms......Page 98
Examples of languages in NP......Page 103
NP-completeness......Page 111
Further NP-complete problems......Page 117
Verifying a polynomial identity......Page 127
Primality testing......Page 131
Randomized complexity classes......Page 136
Information complexity......Page 141
Information complexity......Page 142
Self-delimiting information complexity......Page 147
The notion of a random sequence......Page 151
Kolmogorov complexity, entropy and coding......Page 153
Pseudorandom numbers......Page 161
Classical methods......Page 162
The notion of a pseudorandom number generator......Page 164
One-way functions......Page 168
Discrete square roots......Page 172
Decision trees......Page 175
Algorithms using decision trees......Page 176
Non-deterministic decision trees......Page 181
Lower bounds on the depth of decision trees......Page 184
Models of algebraic computation......Page 191
Arithmetic operations on large numbers......Page 193
Matrix multiplication......Page 195
Inverting matrices......Page 197
Multiplication of polynomials......Page 198
Discrete Fourier transform......Page 200
The complexity of computing square-sums......Page 202
Evaluation of polynomials......Page 203
Formula complexity and circuit complexity......Page 206
Parallel random access machines......Page 209
The class NC......Page 214
Communication complexity......Page 219
Communication matrix and protocol-tree......Page 220
Examples......Page 225
Non-deterministic communication complexity......Page 227
Randomized protocols......Page 231
A classical problem......Page 233
A simple complexity-theoretic model......Page 234
Public-key cryptography......Page 235
The Rivest–Shamir–Adleman code (RSA code)......Page 237
Circuit complexity......Page 241
Lower bound for the Majority Function......Page 242
Monotone circuits......Page 245
How to save the last move in chess?......Page 247
How to use your password – without telling it?......Page 249
How to prove non-existence?......Page 251
How to referee exponentially long papers?......Page 254
Approximability......Page 256