Theory of Computation Book

The Complexity of Computations.- Time and Space Complexity Classes and Savitch’s Theorem.- Separation Results.- Logspace Computability.- The Circuit Value Problem.- The Knaster-Tarski Theorem.- Alternation.- The Polynomial-Time Hierarchy.- Parallel Complexity.- Probabilistic Complexity.- Chinese Remaindering.- Berlekamp’s Algorithm.- Interactive Proofs.- Probabilistically Checkable Proofs.- Complexity of Decidable Theories.- Complexity of the Theory of Real Addition.- Lower Bound for the Theory of Real Addition.- Safra’s Construction.- Relativized Complexity.- Nonexistence of Sparse Complete Sets.- Unique Satisfiability.- Toda’s Theorem.- Lower Bounds for Constant Depth Circuits.- The Switching Lemma.- Tail Bounds.- Applications of the Recursion Theorem.- The Arithmetic Hierarchy.- Complete Problems in the Arithmetic Hierarchy.- Post’s Problem.- The Friedberg–Muchnik Theorem.- The Analytic Hierarchy.- Kleene’s Theorem.- Fair Termination and Harel’s Theorem.- Exercises.- Hints and Solutions.