Contents
Foreword vii
Notation xi
Introduction 1
Part 1. Classical Computation 9
1. Turing machines 9
1.1. Definition of a Turing machine 10
1.2. Computable functions and decidable predicates 11
1.3. Turing’s thesis and universal machines 12
1.4. Complexity classes 14
2. Boolean circuits 17
2.1. Definitions. Complete bases 17
2.2. Circuits versus Turing machines 20
2.3. Basic algorithms. Depth, space and width 23
3. The class NP: Reducibility and completeness 27
3.1. Nondeterministic Turing machines 27
3.2. Reducibility and NP-completeness 30
4. Probabilistic algorithms and the class BPP 36
4.1. Definitions. Amplification of probability 36
4.2. Primality testing 38
4.3. BPP and circuit complexity 42
iii
Previous Page Next Page