| PART I:ALGORITHMS 1 Problems and Algorithms 1.1 Graph reachability 1.2 Maximum flow and matching 1.3 The traveling salesman problem 1.4 Notes,references,and problems 2 Turing machines 2.1 Turing machine basics 2.2 Turing machines as algorithms 2.3 Turing machines with multiple strings 2.4 Linear speedup 2.5 Space bounds 2.6 Random access machines 2.7 Nondeterministic machines 2.8 Notes,references,and problems 3 Undecidability 3.1 Universal Turing machines 3.2 The halting problem 3.3 More undecidability 3.4 Notes,references,and problems PART II:LOGIC 4 Boolean logic 4.1 Boolean Expressions 4.2 Satisfiability and validity 4.3 Boolean functions and circuits 4.4 Notes,references,and problems 5 First-order logic 5.1 The syntax of first-order logic 5.2 Models 5.3 Valid expressions 5.4 Axioms and proofs 5.5 The completeness theorem 5.6 Consequences of the completeness theorem 5.7 Second-order logic 5.8 Notes,references,and problems 6 Undecidability in logic 6.1 Axioms for number theory 6.2 Computation as a number-theoretic concept 6.3 Undecidability and incompleteness 6.4 Notes,references,and problems PART III:P AND NP 7 Relations between complexity classes 7.1 Complexity classes 7.2 The hierarchy theorem 7.3 The reachability method 7.4 Notes,references,and problems 8 Reductions and completeness 8.1 Reductions 8.2 Completeness 8.3 Logical characterizations 8.4 Notes,referencess,and problems 9 NP-complete problems 9.1 Problems in NP 9.2 Variants of satisfiability 9.3 Graph-theoretic problems 9.4 Sets and numbers 9.5 Notes,references,and problems 10 coNP and function problems 10.1 NP and coNP 10.2 Primality 10.3 Function problems 10.4 Notes,references,and problems 11 Randomized computation 11.1 Randomized algorithms 11.2 Randomized complexity classes 11.3 Random sources 11.4 Circuit complexity 11.5 Notes,references,and problems 12 Cryptography 12.1 One-way functions 12.2 Protocols 12.3 Notes,references,and problems 13 Approximability 13.1 Approximation algorithms 13.2 Approximation and complexity 13.3 Nonapproximability 13.4 Notes,references,and problems 14 On P vs.NP 14.1 The map of NP 14.2 Isomorphism and density 14.3 Oracles 14.4 Monotone circuits 14.5 Notes,references,and problems PART IV:INSIDE P 15 Parallel computation 15.1 Parallel algorithms 15.2 Parallel models of computation 15.3 The class NC 15.4 RNC algorithms 15.5 Notes,references,and problems 16 Logarithmic space 16.1 The L=NL problem 16.2 Alternation 16.3 Undirected reachability 16.4 Notes,references,and problems PART V:BEYOND NP 17 The polynomial hierarchy 17.1 Optimization problems 17.2 The hierarchy 17.3 Notes,references,and problems 18 Computation that counts 18.1 The permanent 18.2 The Class P 18.3 Notes,references,and problems 19 Polynomial space 19.1 Alternation and games 19.2 Games against nature and interactive protocols 19.3 More PSPACE-complete problems 19.4 Notes,references,and problems 20 A glimpse beyond 20.1 Exponential time 20.2 Notes,references,and problems Index Author index |
内容加载中，请稍后...
商品评论（0条）