| 1 introduction . 1.1 what is complexity theory? 1.2 didactic background 1.3 overview 1.4 additional literature 2 algorithmic problems & their complexity 2.1 what are algorithmic problems? 2.2 some important algorithmic problems 2.3 measuring computation time 2.4 the complexity of algorithmic problems 3 fundamental complexity classes 3.1 the special role of polynomial computation time 3.2 randomized algorithms 3.3 the fundamental complexity classes for algorithmic problems 3.4 the fundamental complexity classes for decision problems 3.5 nondeterminism as a special case of randomization 4 reductions - algorithmic relationships between problems 4.1 when are two problems algorithmically similar? 4.2 reductions between various variants of a problem 4.3 reductions between related problems .4.4 reductions between unrelated problems 4.5 the special role of polynomial reductions 5 the theory of np-completeness 5.1 fundamental considerations 5.2 problems in np 5.3 alternative characterizations of np 5.4 cook's theorem 6 np-complete and np-equivalent problems 6.1 fundamental considerations 6.2 traveling salesperson problems 6.3 knapsack problems 6.4 partitioning and scheduling problems 6.5 clique problems 6.6 team building problems 6.7 championship problems 7 the complexity analysis of problems 7.1 the dividing line between easy and hard 7.2 pseudo-polynomial algorithms and strong np-completeness 7.3 an overview of the np-completeness proofs considered 8 the complexity of approximation problems - classical results 8.1 complexity classes 8.2 approximation algorithms 8.3 the gap technique 8.4 approximation-preserving reductions 8.5 complete approximation problems 9 the complexity of black box problems 9.1 black box optimization 9.2 yao's minimax principle 9.3 lower bounds for black box complexity 10 additional complexity classes 10.1 fundamental considerations 10.2 complexity classes within np and co-np 10.3 oracle classes .. 10.4 the polynomial hierarchy 10.5 bpp, np, and the polynomial hierarchy 11 interactive proofs 11.1 fundamental considerations 11.2 interactive proof systems 11.3 regarding the complexity of graph isomorphism problems 11.4 zero-knowledge proofs 12 the pcp theorem and the complexity of approximation problems 12.1 randomized verification of proofs 12.2 the pcp theorem 12.3 the pcp theorem and inapproximability results 12.4 the pcp theorem and apx-completeness 13 further topics from classical complexity theory 13.1 overview 13.2 space-bounded complexity classes 13.3 pspace-complete problems 13.4 nondeterminism and determinism in the context of bounded space 13.5 nondeterminism and complementation with precise space bounds 13.6 complexity classes within p 13.7 the complexity of counting problems 14 the complexity of non-uniform problems 14.1 fundamental considerations 14.2 the simulation of turing machines by circuits 14.3 the simulation of circuits by non-uniform turing machines 14.4 branching programs and space bounds 14.5 polynomial circuits for problems in bpp 14.6 complexity classes for computation with help 14.7 are there polynomial circuits for all problems in np? 15 communication complexity 15.1 the communication game 15.2 lower bounds for communication complexity 15.3 nondeterministic communication protocols 15.4 randomized communication protocols 15.5 communication complexity and vlsi circuits 15.6 communication complexity and computation time 16 the complexity of boolean functions 16.1 fundamental considerations 16.2 circuit size 16.3 circuit depth 16.4 the size of depth-bounded circuits 16.5 the size of depth-bounded threshold circuits 16.6 the size of branching programs 16.7 reduction notions final comments a appendix a.1 orders of magnitude and o-notation a.2 results from probability theory references index ... |
内容加载中，请稍后...
商品评论（0条）