Издательство Springer, 2006, -405 pp.
The course serves a dual purpose: to cover core material in the foundations of computing for graduate students in computer science preparing for their PhD qualifying exams, and to provide an introduction to some more advanced topics in the theory of computational complexity for those intending to pursue further study in the area. The course is thus a mixture of core and advanced material.
Most of the course is conceed with computational complexity, or the classification of computational problems in terms of their inherent complexity. This usually refers to time or space usage on a particular computational model, but may include other complexity measures as well, such as randomness, number of alteations, or circuit size or depth. We include a rigorous treatment of computational models, including deterministic, nondeterministic, and alteating Turing machines, circuits, probabilistic machines, interactive proof systems, automata on infinite objects, and various logical formalisms. Also included are various approximation and inapproximation results and some lower bounds. According to most treatments, the complexity universe stops at polynomial space, but we also look at higher levels of complexity all the way up through the primitive recursive functions, partial recursive functions, and the arithmetic and analytic hierarchies.
The Complexity of Computations
Time and Space Complexity Classes and Savitch’s Theorem
Separation Results
The Immerman–Szelepcs?enyi Theorem
Logspace Computability
The Circuit Value Problem
The Knaster–Tarski Theorem
Alteation
Problems Complete for PSPACE
The Polynomial-Time Hierarchy
More on the Polynomial-Time Hierarchy
Parallel Complexity
Relation of NC to Time-Space Classes
Probabilistic Complexity
BPP ? ???2
Chinese Remaindering
Complexity of Primality Testing
Berlekamp’s Algorithm
Interactive Proofs
PSPACE ? IP
IP ? PSPACE
Probabilistically Checkable Proofs
NP ? PCP(n3,1)
More on PCP
A Crash Course in Logic
Complexity of Decidable Theories
Complexity of the Theory of Real Addition
Lower Bound for the Theory of Real Addition
Lower Bound for Integer Addition
Automata on Infinite Strings and S1S
Determinization of ?-Automata
Safra’s Construction
Relativized Complexity
Nonexistence of Sparse Complete Sets
Unique Satisfiability
Toda’s Theorem
Circuit Lower Bounds and Relativized PSPACE=PH
Lower Bounds for Constant Depth Circuits
The Switching Lemma
Tail Bounds
The Gap Theorem and Other Pathology
Partial Recursive Functions and G?odel Numberings
Applications of the Recursion Theorem
Abstract Complexity
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
The course serves a dual purpose: to cover core material in the foundations of computing for graduate students in computer science preparing for their PhD qualifying exams, and to provide an introduction to some more advanced topics in the theory of computational complexity for those intending to pursue further study in the area. The course is thus a mixture of core and advanced material.
Most of the course is conceed with computational complexity, or the classification of computational problems in terms of their inherent complexity. This usually refers to time or space usage on a particular computational model, but may include other complexity measures as well, such as randomness, number of alteations, or circuit size or depth. We include a rigorous treatment of computational models, including deterministic, nondeterministic, and alteating Turing machines, circuits, probabilistic machines, interactive proof systems, automata on infinite objects, and various logical formalisms. Also included are various approximation and inapproximation results and some lower bounds. According to most treatments, the complexity universe stops at polynomial space, but we also look at higher levels of complexity all the way up through the primitive recursive functions, partial recursive functions, and the arithmetic and analytic hierarchies.
The Complexity of Computations
Time and Space Complexity Classes and Savitch’s Theorem
Separation Results
The Immerman–Szelepcs?enyi Theorem
Logspace Computability
The Circuit Value Problem
The Knaster–Tarski Theorem
Alteation
Problems Complete for PSPACE
The Polynomial-Time Hierarchy
More on the Polynomial-Time Hierarchy
Parallel Complexity
Relation of NC to Time-Space Classes
Probabilistic Complexity
BPP ? ???2
Chinese Remaindering
Complexity of Primality Testing
Berlekamp’s Algorithm
Interactive Proofs
PSPACE ? IP
IP ? PSPACE
Probabilistically Checkable Proofs
NP ? PCP(n3,1)
More on PCP
A Crash Course in Logic
Complexity of Decidable Theories
Complexity of the Theory of Real Addition
Lower Bound for the Theory of Real Addition
Lower Bound for Integer Addition
Automata on Infinite Strings and S1S
Determinization of ?-Automata
Safra’s Construction
Relativized Complexity
Nonexistence of Sparse Complete Sets
Unique Satisfiability
Toda’s Theorem
Circuit Lower Bounds and Relativized PSPACE=PH
Lower Bounds for Constant Depth Circuits
The Switching Lemma
Tail Bounds
The Gap Theorem and Other Pathology
Partial Recursive Functions and G?odel Numberings
Applications of the Recursion Theorem
Abstract Complexity
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