P, NP, and NP-completeness: The basics of computational complexity

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 9
List of Figures......Page 13
Preface......Page 15
Overview......Page 19
To the Teacher......Page 23
Notations and Conventions......Page 27
Main Definitions and Results......Page 29
1 Computational Tasks and Models......Page 33
Teaching Notes......Page 34
1.1 Representation......Page 35
1.2.1 Search Problems......Page 37
1.2.2 Decision Problems......Page 38
1.3 Uniform Models (Algorithms)......Page 40
1.3.1 Overview and General Principles......Page 41
1.3.2 A Concrete Model: Turing Machines......Page 43
1.3.2.1 The Actual Model......Page 44
1.3.2.2 The Church-Turing Thesis......Page 48
1.3.3.1 On the Existence of Uncomputable Functions......Page 50
1.3.3.2 The Halting Problem......Page 51
1.3.3.3 A Few More Undecidability Results......Page 53
1.3.4 Universal Algorithms......Page 54
1.3.4.1 The Existence of Universal Algorithms......Page 55
1.3.4.2 A Detour: Kolmogorov Complexity......Page 56
1.3.5 Time (and Space) Complexity......Page 58
1.3.6 Oracle Machines and Turing-Reductions......Page 61
1.4 Non-Uniform Models (Circuits and Advice)......Page 63
1.4.1.1 The Basic Model......Page 64
1.4.1.2 Circuit Complexity......Page 67
1.4.2 Machines That Take Advice......Page 68
1.4.3 Restricted Models......Page 69
1.4.3.1 Boolean Formulae......Page 70
1.4.3.2 Other Restricted Classes of Circuits......Page 71
1.5 Complexity Classes......Page 72
Exercises......Page 73
2 The P versus NP Question......Page 80
Teaching Notes......Page 81
2.1 Efficient Computation......Page 82
2.2 The Search Version: Finding versus Checking......Page 85
2.2.1 The Class P as a Natural Class of Search Problems......Page 86
2.2.2 The Class NP as Another Natural Class of Search Problems......Page 88
2.2.3 The P versus NP Question in Terms of Search Problems......Page 89
2.3 The Decision Version: Proving versus Verifying......Page 90
2.3.2 The Class NP and NP-Proof Systems......Page 91
2.3.3 The P versus NP Question in Terms of Decision Problems......Page 94
2.4 Equivalence of the Two Formulations......Page 95
2.5 Technical Comments Regarding NP......Page 97
2.6 The Traditional Definition of NP......Page 98
2.7 In Support of P Being Different from NP......Page 101
Exercises......Page 102
Exercises......Page 103
3 Polynomial-time Reductions......Page 106
3.1 The General Notion of a Reduction......Page 107
3.1.1 The Actual Formulation......Page 108
3.1.2 Special Cases......Page 109
3.1.3 Terminology and a Brief Discussion......Page 111
3.2 Reducing Optimization Problems to Search Problems......Page 113
3.3 Self-Reducibility of Search Problems......Page 115
3.3.1 Examples......Page 117
3.3.2 Self-Reducibility of NP-Complete Problems......Page 119
3.4 Digest and General Perspective......Page 120
Exercises......Page 121
4 NP-Completeness......Page 128
Teaching Notes......Page 129
4.1 Definitions......Page 130
4.2 The Existence of NP-Complete Problems......Page 131
Bounded Halting and Non-Halting......Page 134
4.3 Some Natural NP-Complete Problems......Page 135
4.3.1 Circuit and Formula Satisfiability: CSAT and SAT......Page 136
4.3.1.1 The NP-Completeness of CSAT......Page 137
4.3.1.2 The NP-Completeness of SAT......Page 141
4.3.2 Combinatorics and Graph Theory......Page 145
4.3.3 Additional Properties of the Standard Reductions......Page 152
4.3.4 On the Negative Application of NP-Completeness......Page 153
4.3.5 Positive Applications of NP-Completeness......Page 154
4.4 NP Sets That Are Neither in P nor NP-Complete......Page 158
4.5 Reflections on Complete Problems......Page 162
Exercises......Page 165
5.1 Promise Problems......Page 174
5.1.1.1 Search Problems with a Promise......Page 175
5.1.1.2 Decision Problems with a Promise......Page 176
5.1.1.3 Reducibility Among Promise Problems......Page 177
5.1.2.1 Formulating Natural Computational Problems......Page 178
5.1.2.3 Non-generic Applications......Page 179
5.1.2.4 Limitations......Page 180
5.1.3 The Standard Convention of Avoiding Promise Problems......Page 181
5.2 Optimal Search Algorithms for NP......Page 183
5.3 The Class coNP and Its Intersection with NP......Page 186
Exercises......Page 190
On Computation and Efficient Computation......Page 197
On NP and NP-Completeness......Page 198
Absolute Goals and Relative Results......Page 201
P, NP, and NP-completeness......Page 202
Some Advanced Topics......Page 203
A.1 Graphs......Page 209
A.2 Boolean Formulae......Page 211
Bibliography......Page 213
Index......Page 215