Elements of computability, decidability and complexity

Preface ............................................................................ 7 Chapter 1. TURING MACHINES ............................................. 9 1. Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2. Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3. Techniques for Constructing Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Use of States to Store Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Use of Multiple Tracks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Test of String Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Shift of Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.5 Use of Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4. Extensions of Turing Machines Which Do Not Increase Their Power . . . . . . . . . . . . 24 4.1 Two-way Infinite Tape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Multitape Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3 Multihead Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Off-line and On-line Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5 Bidimensional and Multidimensional Turing Machines . . . . . . . . . . . . . . . . . . . . . 28 4.6 Nondeterministic versus Deterministic Turing Machines . . . . . . . . . . . . . . . . . . . . 29 5. Restrictions to Turing Machines Which Do Not Diminish Their Power . . . . . . . . . . 32 5.1 One Tape = One Tape + One Read-only Input Tape = Two Stacks . . . . . . . . 32 5.2 Two Stacks = Four Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.3 Four Counters = Two Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4 Turing Machines with Three or Two States Only . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.5 Turing Machines with Three or Two Tape Symbols Only . . . . . . . . . . . . . . . . . . . 38 6. Turing Machines as Language Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7. Turing Computable Functions and Type 0 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 41 8. Multitape Turing Machines and Random Access Memory Machines . . . . . . . . . . . . . 43 9. Other Models of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 10. Church Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Chapter 2. PARTIAL RECURSIVE FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . 57 11. Preliminary Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 12. Primitive Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 13. Partial Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 14. Partial Recursive Functions and Recursively Enumerable Sets . . . . . . . . . . . . . . . . . 75 15. Recursive Enumerable Sets and Turing Computable Functions . . . . . . . . . . . . . . . . . 82 56 16. Partial Recursive Functions on Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 17. Partial Recursive Functions and Turing Computable Functions . . . . . . . . . . . . . . . . 83 18. Subrecursive Classes of Partial Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Chapter 3. DECIDABILITY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 19. Universal Turing Machines and Undecidability of the Halting Problem . . . . . . . . . 89 20. Rice Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 21. Post Correspondence Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 22. Decidability and Undecidability in Formal Languages . . . . . . . . . . . . . . . . . . . . . . . . 103 22.1 Decidable Properties of Deterministic Context-free Languages . . . . . . . . . . . 108 22.2 Undecidable Properties of Deterministic Context-free Languages . . . . . . . . 108 22.3 Summary of Decidability and Undecidability Results in Formal Languages 109 23. Decidability and Undecidability of Tiling Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 24. Undecidability of Satisfiability in First Order Predicate Calculus . . . . . . . . . . . . . 113 25. Arithmetical Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Chapter 4. COMPUTATIONAL COMPLEXITY . . . . . . . . . . . . . . . . . . . . . . . . . . 121 26. Preliminary Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 27. P and NP Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 28. Problem Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 29. NP-complete Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 29.1 Logarithmic-Space versus Polynomial-Time Reductions . . . . . . . . . . . . . . . . . 142 29.2 NP-Complete Problems and Strongly NP-Complete Problems . . . . . . . . . . . 143 29.3 NP Problems and co-NP Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 29.4 Complete Problems and Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 29.5 Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 29.6 Stratification of Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 30. Computational Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 30.1 Deterministic Space and Deterministic Time Hierarchies . . . . . . . . . . . . . . . . 150 30.2 Relationships among Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 30.3 Nondeterministic Space and Nondeterministic Time Hierarchies . . . . . . . . . 152 30.4 Properties of General Complexity Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 30.5 Computations with Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 31. Polynomial Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 32. Invariance with respect to the Computational Model . . . . . . . . . . . . . . . . . . . . . . . . . 155 33. Complexity Classes Based on Randomization and Probability . . . . . . . . . . . . . . . . 161 34. Complexity Classes of Interactive Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 35. Complexity Classes of Parallel Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179