Home Page Icon
Home Page
Table of Contents for
Series
Close
Series
by Ker-I Ko, Ding-Zhu Du
Theory of Computational Complexity, 2nd Edition
Cover
Series
Title Page
Copyright
Preface
Notes on the Second Edition
Part I: Uniform Complexity
Chapter 1: Models of Computation and Complexity Classes
1.1 Strings, Coding, and Boolean Functions
1.2 Deterministic Turing Machines
1.3 Nondeterministic Turing Machines
1.4 Complexity Classes
1.5 Universal Turing Machine
1.6 Diagonalization
1.7 Simulation
Exercises
Historical Notes
Chapter 2: NP-Completeness
2.1 NP
2.2 Cook's Theorem
2.3 More NP-Complete Problems
2.4 Polynomial-Time Turing Reducibility
2.5 NP-Complete Optimization Problems
Exercises
Historical Notes
Chapter 3: The Polynomial-Time Hierarchy and Polynomial Space
3.1 Nondeterministic Oracle Turing Machines
3.2 Polynomial-Time Hierarchy
3.3 Complete Problems in PH
3.4 Alternating Turing Machines
3.5 PSPACE-Complete Problems
3.6 EXP-Complete Problems
Exercises
Historical Notes
Chapter 4: Structure of NP
4.1 Incomplete Problems in NP
4.2 One-Way Functions and Cryptography
4.3 Relativization
4.4 Unrelativizable Proof Techniques
4.5 Independence Results
4.6 Positive Relativization
4.7 Random Oracles
4.8 Structure of Relativized NP
Exercises
Historical Notes
Part II: Nonuniform Complexity
Chapter 5: Decision Trees
5.1 Graphs and Decision Trees
5.2 Examples
5.3 Algebraic Criterion
5.4 Monotone Graph Properties
5.5 Topological Criterion
5.6 Applications of the Fixed Point Theorems
5.7 Applications of Permutation Groups
5.8 Randomized Decision Trees2
5.9 Branching Programs
Exercises
Historical Notes
Chapter 6: Circuit Complexity
6.1 Boolean Circuits
6.2 Polynomial-Size Circuits
6.3 Monotone Circuits
6.4 Circuits with Modulo Gates
6.5 NC
6.6 Parity Function
6.7 P-Completeness
6.8 Random Circuits and RNC
Exercises
Historical Notes
Chapter 7 Polynomial-Time Isomorphism
7.1 Polynomial-Time Isomorphism
7.2 Paddability
7.3 Density of NP-Complete Sets
7.4 Density of EXP-Complete Sets
7.5 One-Way Functions and Isomorphism in EXP
7.6 Density of P-Complete Sets
Exercises
Historical Notes
Part III: Probabilistic Complexity
Chapter 8: Probabilistic Machines and Complexity Classes
8.1 Randomized Algorithms
8.2 Probabilistic Turing Machines
8.3 Time Complexity of Probabilistic Turing Machines
8.4 Probabilistic Machines with Bounded Errors
8.5 BPP and P
8.6 BPP and NP
8.7 BPP and the Polynomial-Time Hierarchy
8.8 Relativized Probabilistic Complexity Classes
Exercises
Historical Notes
Chapter 9: Complexity of Counting
9.1 Counting Class
9.2 -Complete Problems
9.3 and the Polynomial-Time Hierarchy
9.4 and the Polynomial-Time Hierarchy
9.5 Circuit Complexity and Relativized and
9.6 Relativized Polynomial-Time Hierarchy
Exercises
Historical Notes
Chapter 10: Interactive Proof Systems
10.1 Examples and Definitions
10.2 Arthur–Merlin Proof Systems
10.3 AM Hierarchy Versus Polynomial-Time Hierarchy
10.4 IP Versus AM
10.5 IP Versus PSPACE
Exercises
Historical Notes
Chapter 11: Probabilistically Checkable Proofs and NP-Hard Optimization Problems
11.1 Probabilistically Checkable Proofs
11.2 PCP Characterization of NP
11.3 Probabilistic Checking and Inapproximability
11.4 More NP-Hard Approximation Problems
Exercises
Historical Notes
References
References
Index
Series
End User License Agreement
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Contents
Next
Next Chapter
Title Page
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset