计算复杂性的现代方法(英文影印版)

.np and np completeness
2.1 the class np
2.2 reducibility and np-completeness
2.3 the cook-levin theorem: computation is local
2.4 the web of reductions
2.5 decision versus search
2.6 eonp, exp, and nexp
2.7 more thoughts about p, np, and all that
chapter notes and history
exercises
diagonalization
3.1 time hierarchy theorem
3.2 nondeterministic time hierarchy theorem
3.3 ladner's theorem: existence of np-intermediate problems
3.4 oracle machines and the limits of diagonalization
chapter notes and history
exercises
space complexity
4.1 definition of space-bounded computation
4.2 pspace completeness
4.3 nl completeness
chapter notes and history
exercises
5 the polynomial hierarchy and alternations
5.1 the class
5.2 the polynomial hierarchy
5.3 alternating turing machines
5.4 time versus alternations: time-space tradeoffs for sat
5.5 defining the hierarchy via oracle machines
chapter notes and history
exercises
6 boolean circuits
6.1 boolean circuits and p/poly
6.2 uniformly generated circuits
6.3 turing machines that take advice
6.4 p/poly and np
6.5 circuit lower bounds
6.6 nonuniform hierarchy theorem
6.7 finer gradations among circuit classes
6.8 circuits of exponential size
chapter notes and history
exercises
randomized computation
7.1 probabilistic turing machines
7.2 some examples of ptms
7.3 one-sided and "zero-sided" error: rp, corp, zpp
7.4 the robustness of our definitions
7.5 relationship between bpp and other classes
7.6 randomized reductions
7.7 randomized space-bounded computation
chapter notes and history
exercises
8 interactive proofs
8.1 interactive proofs: some variations
8.2 public coins and am
8.3 ip= pspace
8.4 the power of the prover
8.5 multiprover interactive proofs (mip)
8.6 program checking
8.7 interactive proof for the permanent
chapter notes and history
exercises
9 cryptography
9.1 perfect secrecy and its limitations
9.2 computational security, one-way functions, and pseudorandom generators
9.3 pseudorandom generators from one-way permutations
9.4 zero knowledge
9.5 some applications
chapter notes and history
exercises
l0 quantum computation
10.1 quafitum weirdness: the two-slit experiment
10.2 quantum superposition and qubits
10.3 definition of quantum computation and bqp
10.4 grover's search algorithm
10.5 simon's algorithm
10.6 shor's algorithm: integer factorization using quantum computers
10.7 bqp and classical complexity classes
chapter notes and history
exercises
11 pcp theorem and hardness of approximation: an introduction
11.1 motivation: approximate solutions to np-hard optimization problems
11.2 two views of the pcp theorem
11.3 equivalence of the two views
11.4 hardness of approximation for vertex cover and independent set
11.5 np pcp(poly(n), 1): pcp from the walsh-hadamard code
chapter notes and history
exercises
part two: lower bounds for concrete computational models
12 decision trees
12.1 decision trees and decision tree complexity
12.2 certificate complexity
12.3 randomized decision trees
12.4 some techniques for proving decision tree lower bounds
chapter notes and history
exercises
13 communication complexity
13.1 definition of two-party communication complexity
13.2 lower bound methods
13.3 multiparty communication complexity
13.4 overview of other communication models
chapter notes and history
exercises
14 circuit lower bounds: complexity theory's waterloo
14.1 ac~ and hfistad's switching lemma
14.2 circuits with "counters": acc
14.3 lower bounds for monotone circuits
14.4 circuit complexity: the frontier
14.5 approaches using communication complexity
chapter notes and history
exercises
15 proof complexity
15.1 some examples
15.2 propositional calculus and resolution
15.3 other proof systems: a tour d'horizon
15.4 metamathematical musings
chapter notes and history
exercises
16 algebraic computation models
16.1 algebraic straight-line programs and algebraic circuits
16.2 algebraic computation trees
16.3 the blum-shub-smale model
chapter notes and history
exercises
part three: advanced topics
17 complexity of counting
17.1 examples of counting problems
17.2 the class #p
17.3 #p completeness
17.4 toda's theorem: ph _ p#sat
17.5 open problems
chapter notes and history
exercises
18 average case complexity: levin's theory
18.1 distributional problems and distp
18.2 formalization of "real-life distributions"
18.3 di stnp and its complete problems
18.4 philosophical and practical implications
chapter notes and history
exercises
19 hardness amplification and error-correcting codes
19.1 mild to strong hardness: yao's xor lemma
19.2 tool: error-correcting codes
19.3 efficient decoding
19.4 local decoding and hardness amplification
19.5 list decoding
19.6 local list decoding: getting to bpp= p
chapter notes and history
exercises
20 derandomization
20.1 pseudorandom generators and derandomization
20.2 proof of theorem 20.6: nisan-wigderson construction
20.3 derandomization under uniform assumptions
20.4 derandomization requires circuit lower bounds
chapter notes and history
exercises
21 pseudorandom constructions: expanders and extractors
21.1 random walks and eigenvalues
21.2 expander graphs
21.3 explicit construction of expander graphs
21.4 deterministic logspace algorithm for undirected connectivity
21.5 weak random sources and extractors
21.6 pseudorandom generators for space-bounded computation
chapter notes and history
exercises
22 proofs of pcp theorems and the fourier transform technique
22.1 constraint satisfaction problems with nonbinary alphabet
22.2 proof of the pcp theorem
22.3 hardness of 2cs pt: tradeoff between gap and alphabet size
22.4 hastad's 3-bit pcp theorem and hardness of eax-3sat
22.5 tool: the fourier transform technique
22.6 coordinate functions, long code, and its testing
22.7 proof of theorem 22.16
22.8 hardness of approximating set- c0v er
22.9 other pcp theorems: a survey
22.a transforming qcsp instances into "nice" instances
chapter notes and history
exercises
23 why are circuit lower bounds so difficult?
23.1 definition of natural proofs
23.2 what's so natural about natural proofs?
23.3 proof of theorem 23.1
23.4 an "unnatural" lower bound
23.5 a philosophical view
cttapter notes and history
exercises
appendix: mathematical background
a.1 sets, functions, pairs, strings, graphs, logic
a.2 probability theory
a.3 number theory and groups
a.4 finite fields
a.5 basic facts from linear algebra
a.6 polynomials
hints and selected exercises
main theorems and definitions
bibliography
index
complexity class index