| Acknowledgments |
|
xiii | |
| Preface for instructors |
|
xv | |
| The inspiration of GEB |
|
xv | |
| Which "theory" course are we talking about? |
|
xv | |
| The features that might make this book appealing |
|
xvi | |
| What's in and what's out |
|
xvii | |
| Possible courses based on this book |
|
xvii | |
| Computer science as a liberal art |
|
xviii | |
| Overview |
|
1 | (2) |
|
1 Introduction: What Can And Cannot Be Computed? |
|
|
3 | (10) |
|
|
|
4 | (1) |
|
|
|
5 | (1) |
|
1.3 Uncomputable problems |
|
|
6 | (1) |
|
1.4 A more detailed overview of the book |
|
|
6 | (2) |
|
Overview of part I Computability theory |
|
|
6 | (1) |
|
Overview of part II Complexity theory |
|
|
7 | (1) |
|
Overview of part III Origins and applications |
|
|
8 | (1) |
|
1.5 Prerequisites for understanding this book |
|
|
8 | (1) |
|
1.6 The goals of the book |
|
|
9 | (1) |
|
The fundamental goal: What can be computed? |
|
|
9 | (1) |
|
Secondary goal 1 A practical approach |
|
|
9 | (1) |
|
Secondary goal 2 Some historical insight |
|
|
10 | (1) |
|
1.7 Why study the theory of computation? |
|
|
10 | (3) |
|
Reason 1 The theory of computation is useful |
|
|
10 | (1) |
|
Reason 2 The theory of computation is beautiful and important |
|
|
11 | (1) |
|
|
|
11 | (2) |
|
Part I COMPUTABILITY THEORY |
|
|
13 | (180) |
|
2 What Is A Computer Program? |
|
|
15 | (15) |
|
2.1 Some Python program basics |
|
|
15 | (3) |
|
Editing and rerunning a Python program |
|
|
17 | (1) |
|
Running a Python program on input from a file |
|
|
17 | (1) |
|
Running more complex experiments on Python programs |
|
|
18 | (1) |
|
|
|
18 | (3) |
|
Programs that call other functions and programs |
|
|
20 | (1) |
|
2.3 ASCII characters and multiline strings |
|
|
21 | (1) |
|
2.4 Some problematic programs |
|
|
22 | (1) |
|
2.5 Formal definition of Python program |
|
|
23 | (2) |
|
2.6 Decision programs and equivalent programs |
|
|
25 | (1) |
|
2.7 Real-world programs versus SISO Python programs |
|
|
26 | (4) |
|
|
|
27 | (3) |
|
3 Some Impossible Python Programs |
|
|
30 | (15) |
|
3.1 Proof by contradiction |
|
|
30 | (1) |
|
3.2 Programs that analyze other programs |
|
|
31 | (2) |
|
Programs that analyze themselves |
|
|
33 | (1) |
|
3.3 The program yesOnString.py |
|
|
33 | (1) |
|
3.4 The program yesOnSelf.py |
|
|
34 | (2) |
|
3.5 The program notYesOnSelf.py |
|
|
36 | (1) |
|
3.6 yesOnString.py can't exist either |
|
|
37 | (2) |
|
A compact proof that yesOnString.py can't exist |
|
|
37 | (2) |
|
3.7 Perfect bug-finding programs are impossible |
|
|
39 | (2) |
|
3.8 We can still find bugs, but we can't do it perfectly |
|
|
41 | (4) |
|
|
|
42 | (3) |
|
4 What Is A Computational Problem? |
|
|
45 | (26) |
|
4.1 Graphs, alphabets, strings, and languages |
|
|
46 | (7) |
|
|
|
46 | (3) |
|
|
|
49 | (1) |
|
|
|
49 | (1) |
|
|
|
50 | (1) |
|
|
|
51 | (2) |
|
4.2 Defining computational problems |
|
|
53 | (4) |
|
Positive and negative instances |
|
|
55 | (1) |
|
Notation for computational problems |
|
|
56 | (1) |
|
4.3 Categories of computational problems |
|
|
57 | (5) |
|
|
|
57 | (1) |
|
|
|
57 | (1) |
|
|
|
57 | (1) |
|
|
|
58 | (1) |
|
|
|
58 | (1) |
|
Converting between general and decision problems |
|
|
59 | (1) |
|
Complement of a decision problem |
|
|
60 | (1) |
|
Computational problems with two input strings |
|
|
61 | (1) |
|
4.4 The formal definition of "solving" a problem |
|
|
62 | (1) |
|
|
|
63 | (1) |
|
4.5 Recognizing and deciding languages |
|
|
63 | (8) |
|
|
|
65 | (1) |
|
Recursive and recursively enumerable languages |
|
|
66 | (1) |
|
|
|
66 | (5) |
|
5 Turing Machines: The Simplest Computers |
|
|
71 | (32) |
|
5.1 Definition of a Turing machine |
|
|
72 | (7) |
|
|
|
76 | (1) |
|
Accepters and transducers |
|
|
77 | (1) |
|
Abbreviated notation for state diagrams |
|
|
78 | (1) |
|
Creating your own Turing machines |
|
|
78 | (1) |
|
5.2 Some nontrivial Turing machines |
|
|
79 | (7) |
|
|
|
80 | (1) |
|
|
|
81 | (4) |
|
Important lessons from the countCs example |
|
|
85 | (1) |
|
5.3 From single-tape Turing machines to multi-tape Turing machines |
|
|
86 | (5) |
|
Two-tape, single-head Turing machines |
|
|
87 | (1) |
|
|
|
88 | (1) |
|
Multi-tape, single-head Turing machines |
|
|
89 | (1) |
|
Two-tape, two-head Turing machines |
|
|
90 | (1) |
|
5.4 From multi-tape Turing machines to Python programs and beyond |
|
|
91 | (4) |
|
Multi-tape Turing machine → random-access Turing machine |
|
|
92 | (1) |
|
Random-access Turing machine → real computer |
|
|
92 | (3) |
|
Modern computer → Python program |
|
|
95 | (1) |
|
5.5 Going back the other way: Simulating a Turing machine with Python |
|
|
95 | (3) |
|
A serious caveat: Memory limitations and other technicalities |
|
|
97 | (1) |
|
5.6 Classical computers can simulate quantum computers |
|
|
98 | (1) |
|
5.7 All known computers are Turing equivalent |
|
|
98 | (5) |
|
|
|
99 | (4) |
|
6 Universal Computer Programs: Programs That Can Do Anything |
|
|
103 | (13) |
|
6.1 Universal Python programs |
|
|
104 | (1) |
|
6.2 Universal Turing machines |
|
|
105 | (2) |
|
6.3 Universal computation in the real world |
|
|
107 | (3) |
|
6.4 Programs that alter other programs |
|
|
110 | (3) |
|
Ignoring the input and performing a fixed calculation instead |
|
|
112 | (1) |
|
6.5 Problems that are undecidable but recognizable |
|
|
113 | (3) |
|
|
|
114 | (2) |
|
7 Reductions: How To Prove A Problem Is Hard |
|
|
116 | (27) |
|
7.1 A reduction for easiness |
|
|
116 | (2) |
|
7.2 A reduction for hardness |
|
|
118 | (2) |
|
7.3 Formal definition of Turing reduction |
|
|
120 | (2) |
|
|
|
120 | (1) |
|
|
|
121 | (1) |
|
Why is ≤T used to denote a Turing reduction? |
|
|
121 | (1) |
|
Beware the true meaning of "reduction" |
|
|
121 | (1) |
|
7.4 Properties of Turing reductions |
|
|
122 | (1) |
|
7.5 An abundance of uncomputable problems |
|
|
123 | (7) |
|
The variants of YesOnString |
|
|
123 | (3) |
|
The halting problem and its variants |
|
|
126 | (2) |
|
Uncomputable problems that aren't decision problems |
|
|
128 | (2) |
|
7.6 Even more uncomputable problems |
|
|
130 | (4) |
|
The computational problem ComputesF |
|
|
132 | (2) |
|
|
|
134 | (1) |
|
7.7 Uncomputable problems that aren't about programs |
|
|
134 | (1) |
|
7.8 Not every question about programs is uncomputable |
|
|
135 | (1) |
|
7.9 Proof techniques for uncomputability |
|
|
136 | (7) |
|
Technique 1 The reduction recipe |
|
|
137 | (1) |
|
Technique 2 Reduction with explicit Python programs |
|
|
138 | (1) |
|
Technique 3 Apply Rice's theorem |
|
|
139 | (1) |
|
|
|
140 | (3) |
|
8 Nondeterminism: Magic Or Reality? |
|
|
143 | (21) |
|
8.1 Nondeterministic Python programs |
|
|
144 | (4) |
|
8.2 Nondeterministic programs for nondecision problems |
|
|
148 | (1) |
|
|
|
149 | (4) |
|
8.4 Nondeterminism doesn't change what is computable |
|
|
153 | (1) |
|
8.5 Nondeterministic Turing machines |
|
|
154 | (2) |
|
8.6 Formal definition of nondeterministic Turing machines |
|
|
156 | (2) |
|
8.7 Models of nondeterminism |
|
|
158 | (1) |
|
8.8 Unrecognizable problems |
|
|
158 | (1) |
|
8.9 Why study nondeterminism? |
|
|
159 | (5) |
|
|
|
160 | (4) |
|
9 Finite Automata: Computing With Limited Resources |
|
|
164 | (29) |
|
9.1 Deterministic finite automata |
|
|
164 | (3) |
|
9.2 Nondeterministic finite automata |
|
|
167 | (3) |
|
|
|
168 | (1) |
|
Formal definition of an nfa |
|
|
169 | (1) |
|
How does an nfa accept a string? |
|
|
170 | (1) |
|
Sometimes nfas make things easier |
|
|
170 | (1) |
|
9.3 Equivalence of nfas and dfas |
|
|
170 | (5) |
|
Nondeterminism can affect computability: The example of pdas |
|
|
173 | (1) |
|
Practicality of converted nfas |
|
|
174 | (1) |
|
Minimizing the size of dfas |
|
|
175 | (1) |
|
|
|
175 | (6) |
|
|
|
176 | (1) |
|
Standard regular expressions |
|
|
177 | (1) |
|
Converting between regexes and finite automata |
|
|
178 | (3) |
|
9.5 Some languages aren't regular |
|
|
181 | (2) |
|
The nonregular language GnTn |
|
|
181 | (2) |
|
The key difference between Turing machines and finite automata |
|
|
183 | (1) |
|
9.6 Many more nonregular languages |
|
|
183 | (4) |
|
|
|
185 | (2) |
|
9.7 Combining regular languages |
|
|
187 | (6) |
|
|
|
188 | (5) |
|
Part II COMPUTATIONAL COMPLEXITY THEORY |
|
|
193 | (122) |
|
10 Complexity Theory: When Efficiency Does Matter |
|
|
195 | (33) |
|
10.1 Complexity theory uses asymptotic running times |
|
|
195 | (2) |
|
|
|
197 | (7) |
|
Dominant terms of functions |
|
|
199 | (2) |
|
A practical definition of big-O notation |
|
|
201 | (1) |
|
Superpolynomial and subexponential |
|
|
202 | (1) |
|
Other asymptotic notation |
|
|
202 | (1) |
|
Composition of polynomials is polynomial |
|
|
203 | (1) |
|
Counting things with big-O |
|
|
203 | (1) |
|
10.3 The running time of a program |
|
|
204 | (6) |
|
Running time of a Turing machine |
|
|
204 | (2) |
|
Running time of a Python program |
|
|
206 | (3) |
|
The lack of rigor in Python running times |
|
|
209 | (1) |
|
10.4 Fundamentals of determining time complexity |
|
|
210 | (7) |
|
A crucial distinction: The length of the input versus the numerical value of the input |
|
|
210 | (2) |
|
The complexity of arithmetic operations |
|
|
212 | (2) |
|
Beware of constant-time arithmetic operations |
|
|
214 | (1) |
|
The complexity of factoring |
|
|
215 | (1) |
|
The importance of the hardness of factoring |
|
|
216 | (1) |
|
The complexity of sorting |
|
|
217 | (1) |
|
10.5 For complexity, the computational model does matter |
|
|
217 | (4) |
|
Simulation costs for common computational models |
|
|
217 | (1) |
|
Multi-tape simulation has quadratic cost |
|
|
218 | (1) |
|
Random-access simulation has cubic cost |
|
|
219 | (1) |
|
Universal simulation has logarithmic cost |
|
|
219 | (1) |
|
Real computers cost only a constant factor |
|
|
220 | (1) |
|
Python programs cost the same as real computers |
|
|
220 | (1) |
|
Python programs can simulate random-access Turing machines efficiently |
|
|
220 | (1) |
|
Quantum simulation may have exponential cost |
|
|
220 | (1) |
|
All classical computational models differ by only polynomial factors |
|
|
221 | (1) |
|
Our standard computational model: Python programs |
|
|
221 | (1) |
|
|
|
221 | (7) |
|
|
|
224 | (4) |
|
11 Poly And Expo: The Two Most Fundamental Complexity Classes |
|
|
228 | (22) |
|
11.1 Definitions of Poly and Expo |
|
|
228 | (2) |
|
Poly and Expo compared to P, Exp, and FP |
|
|
229 | (1) |
|
11.2 Poly is a subset of Expo |
|
|
230 | (1) |
|
11.3 A first look at the boundary between Poly and Expo |
|
|
231 | (7) |
|
|
|
231 | (1) |
|
Traveling salespeople and shortest paths |
|
|
232 | (3) |
|
Multiplying and factoring |
|
|
235 | (1) |
|
Back to the boundary between Poly and Expo |
|
|
235 | (2) |
|
Primality testing is in Poly |
|
|
237 | (1) |
|
11.4 Poly and Expo don't care about the computational model |
|
|
238 | (1) |
|
11.5 HaltEx: A decision problem in Expo but not Poly |
|
|
238 | (5) |
|
11.6 Other problems that are outside Poly |
|
|
243 | (1) |
|
11.7 Unreasonable encodings of the input affect complexity |
|
|
244 | (1) |
|
11.8 Why study Poly, really? |
|
|
245 | (5) |
|
|
|
246 | (4) |
|
12 PolyCheck And NPoly: Hard Problems That Are Easy To Verify |
|
|
250 | (22) |
|
|
|
250 | (4) |
|
|
|
253 | (1) |
|
|
|
254 | (2) |
|
Bounding the length of proposed solutions and hints |
|
|
255 | (1) |
|
Verifying negative instances in exponential time |
|
|
255 | (1) |
|
Solving arbitrary instances in exponential time |
|
|
255 | (1) |
|
12.3 The complexity class PolyCheck |
|
|
256 | (2) |
|
Some PolyCheck examples: packing, SubsetSum, and Partition |
|
|
256 | (1) |
|
The haystack analogy for PolyCheck |
|
|
257 | (1) |
|
12.4 The complexity class NPoly |
|
|
258 | (1) |
|
12.5 PolyCheck and NPoly are identical |
|
|
259 | (4) |
|
Every PolyCheck problem is in NPoly |
|
|
259 | (1) |
|
Every NPoly problem is in PolyCheck |
|
|
260 | (3) |
|
12.6 The PolyCheck/NPoly sandwich |
|
|
263 | (1) |
|
12.7 Nondeterminism does seem to change what is computable efficiently |
|
|
264 | (1) |
|
12.8 The fine print about NPoly |
|
|
265 | (7) |
|
An alternative definition of NPoly |
|
|
265 | (1) |
|
NPoly compared to NP and FNP |
|
|
266 | (2) |
|
|
|
268 | (4) |
|
13 Polynomial-Time Mapping Reductions: Proving X Is As Easy As Y |
|
|
272 | (22) |
|
13.1 Definition of polytime mapping reductions |
|
|
272 | (3) |
|
Polyreducing to nondecision problems |
|
|
275 | (1) |
|
13.2 The meaning of polynomial-time mapping reductions |
|
|
275 | (1) |
|
13.3 Proof techniques for polyreductions |
|
|
276 | (1) |
|
13.4 Examples of polyreductions using Hamilton cycles |
|
|
277 | (4) |
|
A polyreduction from Uhc to Dhc |
|
|
278 | (1) |
|
A polyreduction from Dhc to Uhc |
|
|
279 | (2) |
|
13.5 Three satisfiability problems: CircuitSat, Sat, and 3-Sat |
|
|
281 | (4) |
|
Why do we study satisfiability problems? |
|
|
281 | (1) |
|
|
|
281 | (1) |
|
|
|
282 | (2) |
|
|
|
284 | (1) |
|
ASCII representation of Boolean formulas |
|
|
284 | (1) |
|
|
|
285 | (1) |
|
13.6 Polyreductions between CircuitSat, Sat, and 3-Sat |
|
|
285 | (5) |
|
The Tseytin transformation |
|
|
285 | (5) |
|
13.7 Polyequivalence and its consequences |
|
|
290 | (4) |
|
|
|
291 | (3) |
|
14 NP-Completeness: Most Hard Problems Are Equally Hard |
|
|
294 | (21) |
|
|
|
294 | (2) |
|
|
|
296 | (2) |
|
Reformulations of P versus NP using NP-completeness |
|
|
298 | (1) |
|
|
|
298 | (3) |
|
14.4 Consequences of P=NP |
|
|
301 | (1) |
|
14.5 CircuitSat is a "hardest" NP problem |
|
|
302 | (4) |
|
14.6 NP-completeness is widespread |
|
|
306 | (2) |
|
14.7 Proof techniques for NP-completeness |
|
|
308 | (1) |
|
14.8 The good news and bad news about NP-completeness |
|
|
309 | (6) |
|
Problems in NPoly but probably not NP-hard |
|
|
309 | (1) |
|
Some problems that are in P |
|
|
309 | (1) |
|
Some NP-hard problems can be approximated efficiently |
|
|
310 | (1) |
|
Some NP-hard problems can be solved efficiently for real-world inputs |
|
|
310 | (1) |
|
Some NP-hard problems can be solved in pseudo-polynomial time |
|
|
310 | (1) |
|
|
|
311 | (4) |
|
Part III ORIGINS AND APPLICATIONS |
|
|
315 | (58) |
|
15 The Original Turing Machine |
|
|
317 | (15) |
|
15.1 Turing's definition of a "computing machine" |
|
|
318 | (6) |
|
15.2 Machines can compute what humans can compute |
|
|
324 | (3) |
|
15.3 The Church--Turing thesis: A law of nature? |
|
|
327 | (5) |
|
The equivalence of digital computers |
|
|
327 | (1) |
|
Church's thesis: The equivalence of computer programs and algorithms |
|
|
328 | (1) |
|
Turing's thesis: The equivalence of computer programs and human brains |
|
|
329 | (1) |
|
Church-Turing thesis: The equivalence of all computational processes |
|
|
329 | (1) |
|
|
|
330 | (2) |
|
16 You Can't Prove Everything That's True |
|
|
332 | (21) |
|
The history of computer proofs |
|
|
332 | (1) |
|
|
|
333 | (7) |
|
|
|
336 | (2) |
|
Consistency and completeness |
|
|
338 | (1) |
|
Decidability of logical systems |
|
|
339 | (1) |
|
16.2 Arithmetic as a logical system |
|
|
340 | (5) |
|
Converting the halting problem to a statement about integers |
|
|
341 | (2) |
|
Recognizing provable statements about integers |
|
|
343 | (1) |
|
The consistency of Peano arithmetic |
|
|
344 | (1) |
|
16.3 The undecidability of mathematics |
|
|
345 | (1) |
|
16.4 The incompleteness of mathematics |
|
|
346 | (3) |
|
16.5 What have we learned and why did we learn it? |
|
|
349 | (4) |
|
|
|
350 | (3) |
|
|
|
353 | (17) |
|
|
|
353 | (2) |
|
17.2 Karp's definition of NP-completeness |
|
|
355 | (2) |
|
17.3 The list of 21 NP-complete problems |
|
|
357 | (2) |
|
17.4 Reductions between the 21 NP-complete problems |
|
|
359 | (8) |
|
Polyreducing Sat to Clique |
|
|
361 | (2) |
|
Polyreducing Clique to Node Cover |
|
|
363 | (1) |
|
|
|
364 | (1) |
|
Polyreducing Sat to 3-Sat |
|
|
365 | (1) |
|
Polyreducing Knapsack to Partition |
|
|
365 | (2) |
|
17.5 The rest of the paper: NP-hardness and more |
|
|
367 | (3) |
|
|
|
367 | (3) |
|
18 Conclusion: What Will Be Computed? |
|
|
370 | (3) |
|
18.1 The big ideas about what can be computed |
|
|
370 | (3) |
| Bibliography |
|
373 | (2) |
| Index |
|
375 | |
