Theory of Computation

Description

This textbook is uniquely written with dual purpose. It cover cores material in the foundations of computing for graduate students in computer science and also provides an introduction to some more advanced topics for those intending further study in the area. This innovative text focuses primarily on computational complexity theory: the classification of computational problems in terms of their inherent complexity. The book contains an invaluable collection of lectures for first-year graduates on the theory of computation. Topics and features include more than 40 lectures for first year graduate students, and a dozen homework sets and exercises. Cover Frontmatter Copyright Author’s Dedication Preface Overview and Goals Intended Audience Organization and Features Acknowledgments Contents Lectures Lecture 1: The Complexity of Computations Turing Machines The One-Tape Turing Machine: A Quick Review Crossing Sequences Lecture 2: Time and Space Complexity Classes and Savitch’s Theorem Linear Speedup Some Common Complexity Classes Basic Inclusions Savitch’s Theorem Lecture 3: Separation Results Deterministic Separation Results Nondeterministic Separation Results A Space-Constructible Function S(n) ≤ O(log log n) Lecture 4: The Immerman–Szelepcsényi Theorem Lecture 5: Logspace Computability Logspace Transducers Logspace Reducibility Completeness Lecture 6: The Circuit Value Problem The Cook–Levin Theorem Supplementary Lecture A: The Knaster–Tarski Theorem Transfinite Ordinals Set-Theoretic Definition of Ordinals Transfinite Induction Zorn’s Lemma and the Axiom of Choice Complete Lattices Monotone, Continuous, and Finitary Operators Prefixpoints and Fixpoints Closure Operators The Knaster–Tarski Theorem Lecture 7: Alternation Alternating Complexity Classes Complexity Results Lecture 8: Problems Complete for PSPACE Complexity of Games Lecture 9: The Polynomial-Time Hierarchy Definition of PH in Terms of ATMs Generic Complete Problems Oracle Machines and Relativized Complexity Classes Definition of PH in Terms of Oracle Machines Lecture 10: More on the Polynomial-Time Hierarchy Lecture 11: Parallel Complexity Uniform Families of Circuits and NC Boolean Matrix Multiplication Reflexive Transitive Closure Relation to Time-Space Classes Lecture 12: Relation of NC to Time-Space Classes Lecture 13: Probabilistic Complexity Discrete Probability Probabilistic Turing Machines Probabilistic Tests with Polynomials Lecture 14: BPP ⊆ Σ₂ᵖ ∩ Π₂ᵖ Amplification BPP ⊆ Σ₂ᵖ ∩ Π₂ᵖ Supplementary Lecture B: Chinese Remaindering A Stronger Version Supplementary Lecture C: Complexity of Primality Testing Primality Testing Supplementary Lecture D: Berlekamp’s Algorithm Representation The Factorization Problem Lecture 15: Interactive Proofs Interactive Proof Systems Examples of Interactive Proofs Lecture 16: PSPACE ⊆ IP Lecture 17: IP ⊆ PSPACE Lecture 18: Probabilistically Checkable Proofs PCP and Hardness of Approximation Lecture 19: NP ⊆ PCP(n³,1) Arithmetization Linearity Testing Random Self-Correction Lecture 20: More on PCP Supplementary Lecture E: A Crash Course in Logic What Is Logic? Relational Structures Syntax Terms Valuations and the Meaning of Terms Formulas and Sentences Scope, Free and Bound Occurrences of Variables Interpretation of Formulas and Sentences Prenex Form First-Order Theories Axiomatization The Decision Problem Lecture 21: Complexity of Decidable Theories Ehrenfeucht–Fraissé Games Dense Linear Order Without Endpoints Back and Forth A Decision Procedure Lecture 22: Complexity of the Theory of Real Addition Lecture 23: Lower Bound for the Theory of Real Addition Constructing Short Formulas for Large Integers Encoding Multiplication Bitstring Manipulation Lecture 24: Lower Bound for Integer Addition Encoding Huge Numbers Chinese Remaindering Lecture 25: Automata on Infinite Strings and S1S Automata on Infinite Strings Muller Automata Encoding S1S with Automata Undecidability of the Dyadic Theory Lecture 26: Determinization of ω-Automata Rabin Automata Lecture 27: Safra’s Construction Lecture 28: Relativized Complexity Rise and Fall of the Random Oracle Hypothesis Relativized Pᴬ = NPᴬ Lecture 29: Nonexistence of Sparse Complete Sets Mahaney’s Theorem Supplementary Lecture F: Unique Satisfiability Unique Satisfiability and General Satisfiability Supplementary Lecture G: Toda’s Theorem Counting Classes Toda’s Theorem Lecture 30: Circuit Lower Bounds and Relativized PSPACE = PH Parity and the Class AC⁰ Separating PH from PSPACE Lower Bounds for Parity Lecture 31: Lower Bounds for Constant Depth Circuits Supplementary Lecture H: The Switching Lemma Supplementary Lecture I: Tail Bounds Proof of the Chernoff Bound Lecture 32: The Gap Theorem and Other Pathology Lecture 33: Partial Recursive Functions and Gödel Numberings Partial and Total Recursive Functions Pairing Basic Closure Properties Gödel Numberings Comp, Const, and Pair The Recursion Theorem Lecture 34: Applications of the Recursion Theorem A Self-Printing Program Rice’s Theorem Minimal Programs Effective Padding The Isomorphism Theorem Supplementary Lecture J: Abstract Complexity Lecture 35: The Arithmetic Hierarchy Reducibility and Completeness Lecture 36: Complete Problems in the Arithmetic Hierarchy Lecture 37: Post’s Problem T- and m-degrees Immune, Simple, and Productive Sets Proof of Post’s Theorem Lecture 38: The Friedberg–Muchnik Theorem Low Sets A Finite Injury Priority Argument Lecture 39: The Analytic Hierarchy Definition of Π₁¹ Inductive Definability and the Programming Language IND Inductive and Hyperelementary Relations Lecture 40: Kleene’s Theorem Recursive Trees, Recursive Ordinals, and ω₁ᶜᵏ Kleene’s Theorem Inductive Is Existential over Hyperelementary Lecture 41: Fair Termination and Harel’s Theorem Fair Termination Proof Rules for Fair Termination Harel’s Theorem Exercises Homework 1 Homework 2 Homework 3 Homework 4 Homework 5 Homework 6 Homework 7 Homework 8 Homework 9 Homework 10 Homework 11 Homework 12 Miscellaneous Exercises Hints and Solutions Homework 1 Solutions Homework 2 Solutions Homework 3 Solutions Homework 4 Solutions Homework 5 Solutions Homework 6 Solutions Homework 7 Solutions Homework 8 Solutions Homework 9 Solutions Homework 10 Solutions Homework 11 Solutions Homework 12 Solutions Hints for Selected Miscellaneous Exercises Solutions to Selected Miscellaneous Exercises References Notation and Abbreviations Index