| 理论计算机科学领域的名著 内容严谨，可读性强 注重概念性问题 是研究人员及专家不可或缺的参考文献 |
| Oded Goldreich 以色列魏茨曼科学研究院（Weizmann Institute of Science）计算机科学教授，Meyer W. Weisgal讲席教授。他是SIAM Journal on Computing、Journal of Cryptology和Computational Complexity杂志的特约编辑。 |
| 1 introduction and preliminaries 1 1.1 introduction 1 1.1.1 a brief overview of complexity theory 2 1.1.2 characteristics of complexity theory 6 1.1.3 contents of this book 8 1.1.4 approach and style of this book 12 1.1.5 standard notations and other conventions 16 1.2 computational tasks and models 17 1.2.1 representation 18 1.2.2 computational tasks 18 1.2.3 uniform models (algorithms) 20 1.2.4 non-uniform models (circuits and advice) 36 1.2.5 complexity classes 42 chapter notes 43 2 p, np, and np-completeness 44 2.1 the p versus np question 46 2.1.1 the search version: finding versus checking 47 2.1.2 the decision version: proving versus verifying 50 2.1.3 equivalence of the two formulations 54 2.1.4 two technical comments regarding np 55 2.1.5 the traditional definition of np 55 2.1.6 in support of p different from np 57 2.1.7 philosophical meditations 58 2.2 polynomial-time reductions 58 2.2.1 the general notion of a reduction 59 2.2.2 reducing optimization problems to search problems 61 2.2.3 self-reducibility of search problems 63 2.2.4 digest and general perspective 67 2.3 np-completeness 67 2.3.1 definitions 68 2.3.2 the existence of np-complete problems 69 2.3.3 some natural np-complete problems 71 2.3.4 np sets that are neither in p nor np-complete 81 2.3.5 reflections on complete problems 85 2.4 three relatively advanced topics 87 2.4.1 promise problems 87 2.4.2 optimal search algorithms for np 92 2.4.3 the class conp and its intersection with np 94 chapter notes 97 exercises 99 3 variations on p and np 108 3.1 non-uniform polynomial time (p/poly) 108 3.1.1 boolean circuits 109 3.1.2 machines that take advice 111 3.2 the polynomial-time hierarchy (ph) 113 3.2.1 alternation of quantifiers 114 3.2.2 non-deterministic oracle machines 117 3.2.3 the p/poly versus np question and ph 119 chapter notes 121 exercises 122 4 more resources, more power 127 4.1 non-uniform complexity hierarchies 128 4.2 time hierarchies and gaps 129 4.2.1 time hierarchies 129 4.2.2 time gaps and speedup 136 4.3 space hierarchies and gaps 139 chapter notes 139 exercises 140 5 space complexity 143 5.1 general preliminaries and issues 144 5.1.1 important conventions 144 5.1.2 on the minimal amount of useful computation space 145 5.1.3 time versus space 146 5.1.4 circuit evaluation 153 5.2 logarithmic space 153 5.2.1 the class l 154 5.2.2 log-space reductions 154 5.2.3 log-space uniformity and stronger notions 155 5.2.4 undirected connectivity 155 5.3 non-deterministic space complexity 162 5.3.1 two models 162 5.3.2 nl and directed connectivity 164 5.3.3 a retrospective discussion 171 5.4 pspace and games 172 chapter notes 175 exercises 175 6 randomness and counting 184 7 the bright side of hardness 241 8 pseudorandom generators 284 9 probabilistic proof systems 349 10 relaxing the requirements 416 epilogue 461 appendix a: glossary of complexity classes 463 appendix b: on the quest for lower bounds 469 appendix c: on the foundations of modern cryptography 482 appendix d: probabilistic preliminaries and advanced topics inrandomization 523 appendix e: explicit constructions 545 appendix f: some omitted proofs 566 appendix g: some computational problems 583 bibliography 589 index 60 |
内容加载中，请稍后...
商品评论（0条）