Computational complexity : a conceptual perspective

所蔵情報QRコード

Computational complexity : a conceptual perspective / Oded Goldreich

資料種別:: 電子ブック
形態:: 1 online resource (xxiv, 606 p.)
著者名:: Goldreich, Oded
ISBN:: 9780511804106 [0511804105] (: electronic bk)
書誌ID:: EB00000243

子書誌情報

フルテキスト

所蔵情報

書誌詳細

注記:

Title from publisher's bibliographic system (viewed on 05 Oct 2015).

主題:

Computational complexity; Turing machines

言語:

英語

目次情報:

Introduction and preliminaries / 1：

P, NP and NP-completeness / 2：

Variations on P and NP / 3：

More resources, more power? / 4：

Space complexity / 5：

Randomness and counting / 6：

The bright side of hardness / 7：

Pseudorandom generators / 8：

Probabilistic proof systems / 9：

Relaxing the requirements / 10：

Epilogue

Glossary of complexity classes / A：

On the quest for lower bounds / B：

On the foundations of modern cryptography / C：

Probabilistic preliminaries and advanced topics in randomization / D：

Explicit constructions / E：

Some omitted proofs / F：

Some computational problems / G：

List of Figures

Preface

Organization and Chapter Summaries

Acknowledgments

Introduction and Preliminaries

Introduction / 1.1：

A Brief Overview of Complexity Theory / 1.1.1：

Characteristics of Complexity Theory / 1.1.2：

Contents of This Book / 1.1.3：

Approach and Style of This Book / 1.1.4：

Standard Notations and Other Conventions / 1.1.5：

Computational Tasks and Models / 1.2：

Representation / 1.2.1：

Computational Tasks / 1.2.2：

Uniform Models (Algorithms) / 1.2.3：

Non-uniform Models (Circuits and Advice) / 1.2.4：

Complexity Classes / 1.2.5：

Chapter Notes

P, NP, and NP-Completeness

The P Versus NP Question / 2.1：

The Search Version: Finding Versus Checking / 2.1.1：

The Decision Version: Proving Versus Verifying / 2.1.2：

Equivalence of the Two Formulations / 2.1.3：

Two Technical Comments Regarding NP / 2.1.4：

The Traditional Definition of NP / 2.1.5：

In Support of P Different from NP / 2.1.6：

Philosophical Meditations / 2.1.7：

Polynomial-Time Reductions / 2.2：

The General Notion of a Reduction / 2.2.1：

Reducing Optimization Problems to Search Problems / 2.2.2：

Self-Reducibility of Search Problems / 2.2.3：

Digest and General Perspective / 2.2.4：

NP-Completeness / 2.3：

Definitions / 2.3.1：

The Existence of NP-Complete Problems / 2.3.2：

Some Natural NP-Complete Problems / 2.3.3：

NP Sets That Are Neither in P nor NP-Complete / 2.3.4：

Reflections on Complete Problems / 2.3.5：

Three Relatively Advanced Topics / 2.4：

Promise Problems / 2.4.1：

Optimal Search Algorithms for NP / 2.4.2：

The Class coNP and Its Intersection with NP / 2.4.3：

Exercises

Non-uniform Polynomial Time (P/poly) / 3.1：

Boolean Circuits / 3.1.1：

Machines That Take Advice / 3.1.2：

The Polynomial-Time Hierarchy (PH) / 3.2：

Alternation of Quantifiers / 3.2.1：

Non-deterministic Oracle Machines / 3.2.2：

The P/poly Versus NP Question and PH / 3.2.3：

More Resources, More Power?

Non-uniform Complexity Hierarchies / 4.1：

Time Hierarchies and Gaps / 4.2：

Time Hierarchies / 4.2.1：

Time Gaps and Speedup / 4.2.2：

Space Hierarchies and Gaps / 4.3：

Space Complexity

General Preliminaries and Issues / 5.1：

Important Conventions / 5.1.1：

On the Minimal Amount of Useful Computation Space / 5.1.2：

Time Versus Space / 5.1.3：

Circuit Evaluation / 5.1.4：

Logarithmic Space / 5.2：

The Class L / 5.2.1：

Log-Space Reductions / 5.2.2：

Log-Space Uniformity and Stronger Notions / 5.2.3：

Undirected Connectivity / 5.2.4：

Non-deterministic Space Complexity / 5.3：

Two Models / 5.3.1：

NL and Directed Connectivity / 5.3.2：

A Retrospective Discussion / 5.3.3：

PSPACE and Games / 5.4：

Randomness and Counting

Probabilistic Polynomial Time / 6.1：

Basic Modeling Issues / 6.1.1：

Two-Sided Error: The Complexity Class BPP / 6.1.2：

One-Sided Error: The Complexity Classes RP and coRP / 6.1.3：

Zero-Sided Error: The Complexity Class ZPP / 6.1.4：

Randomized Log-Space / 6.1.5：

Counting / 6.2：

Exact Counting / 6.2.1：

Approximate Counting / 6.2.2：

Searching for Unique Solutions / 6.2.3：

Uniform Generation of Solutions / 6.2.4：

The Bright Side of Hardness

One-Way Functions / 7.1：

Generating Hard Instances and One-Way Functions / 7.1.1：

Amplification of Weak One-Way Functions / 7.1.2：

Hard-Core Preicates / 7.1.3：

Reflections on Hardness Amplification / 7.1.4：

Hard Problems in E / 7.2：

Amplification with Respect to Polynomial-Size Circuits / 7.2.1：

Amplification with Respect to Exponential-Size Circuits / 7.2.2：

Pseudorandom Generators

The General Paradigm / 8.1：

General-Purpose Pseudorandom Generators / 8.2：

The Basic Definition / 8.2.1：

The Archetypical Application / 8.2.2：

Computational Indistinguishability / 8.2.3：

Amplifying the Stretch Function / 8.2.4：

Constructions / 8.2.5：

Non-uniformly Strong Pseudorandom Generators / 8.2.6：

Stronger Notions and Conceptual Reflections / 8.2.7：

Derandomization of Time-Complexity Classes / 8.3：

Defining Canonical Derandomizers / 8.3.1：

Constructing Canonical Derandomizers / 8.3.2：

Technical Variations and Conceptual Reflections / 8.3.3：

Space-Bounded Distinguishers / 8.4：

Definitional Issues / 8.4.1：

Two Constructions / 8.4.2：

Special-Purpose Generators / 8.5：

Pairwise Independence Generators / 8.5.1：

Small-Bias Generators / 8.5.2：

Random Walks on Expanders / 8.5.3：

Probabilistic Proof Systems

Interactive Proof Systems / 9.1：

Motivation and Perspective / 9.1.1：

Definition / 9.1.2：

The Power of Interactive Proofs / 9.1.3：

Variants and Finer Structure: An Overview / 9.1.4：

On Computationally Bounded Provers: An Overview / 9.1.5：

Zero-Knowledge Proof Systems / 9.2：

The Power of Zero-Knowledge / 9.2.1：

Proofs of Knowledge - A Parenthetical Subsection / 9.2.3：

Probabilistically Checkable Proof Systems / 9.3：

The Power of Probabilistically Checkable Proofs / 9.3.1：

PCP and Approximation / 9.3.3：

More on PCP Itself: An Overview / 9.3.4：

Relaxing the Requirements

Approximation / 10.1：

Search or Optimization / 10.1.1：

Decision or Property Testing / 10.1.2：

Average-Case Complexity / 10.2：

The Basic Theory / 10.2.1：

Ramifications / 10.2.2：

Glossary of Complexity Classes / Appendix A：

Preliminaries / A.1：

Algorithm-Based Classes / A.2：

Time Complexity Classes / A.2.1：

Space Complexity Classes / A.2.2：

Circuit-Based Classes / A.3：

On the Quest for Lower Bounds / Appendix B：

Boolean Circuit Complexity / B.1：

Basic Results and Questions / B.2.1：

Monotone Circuits / B.2.2：

Bounded-Depth Circuits / B.2.3：

Formula Size / B.2.4：

Arithmetic Circuits / B.3：

Univariate Polynomials / B.3.1：

Multivariate Polynomials / B.3.2：

Proof Complexity / B.4：

Logical Proof Systems / B.4.1：

Algebraic Proof Systems / B.4.2：

Geometric Proof Systems / B.4.3：

On the Foundations of Modern Cryptography / Appendix C：

The Underlying Principles / C.1：

The Computational Model / C.1.2：

Organization and Beyond / C.1.3：

Computational Difficulty / C.2：

Hard-Core Predicates / C.2.1：

Pseudorandomness / C.3：

Pseudorandom Functions / C.3.1：

Zero-Knowledge / C.4：

The Simulation Paradigm / C.4.1：

The Actual Definition / C.4.2：

A General Result and a Generic Application / C.4.3：

Definitional Variations and Related Notions / C.4.4：

Encryption Schemes / C.5：

Beyond Eavesdropping Security / C.5.1：

Signatures and Message Authentication / C.6：

General Cryptographic Protocols / C.6.1：

The Definitional Approach and Some Models / C.7.1：

Some Known Results / C.7.2：

Construction Paradigms and Two Simple Protocols / C.7.3：

Concluding Remarks / C.7.4：

Probabilistic Preliminaries and Advanced Topics in Randomization / Appendix D：

Probabilistic Preliminaries / D.1：

Notational Conventions / D.1.1：

Three Inequalities / D.1.2：

Hashing / D.2：

The Leftover Hash Lemma / D.2.1：

Sampling / D.3：

Formal Setting / D.3.1：

Known Results / D.3.2：

Hitters / D.3.3：

Randomnes Extractors / D.4：

Definitions and Various Perspectives / D.4.1：

Explicit Constructions / D.4.2：

Error-Correcting Codes / E.1：

Basic Notions / E.1.1：

A Few Popular Codes / E.1.2：

Two Additional Computational Problems / E.1.3：

A List-Decoding Bound / E.1.4：

Expander Graphs / E.2：

Definitions and Properties / E.2.1：

Some Omitted Proofs / E.2.2：

Proving That PH Reduces to #P / F.1：

Proving That IP(f) [characters not reproducible] AM(O(f)) [characters not reproducible] AM(f) / F.2：

Emulating General Interactive Proofs by AM-Games / F.2.1：

Linear Speedup for AM / F.2.2：

Some Computational Problems / Appendix G：

Graphs / G.1：

Boolean Formulae / G.2：

Finite Fields, Polynomials, and Vector Spaces / G.3：

The Determinant and the Permanent / G.4：

Primes and Composite Numbers / G.5：

Bibliography

Index

Introduction and preliminaries / 1：

P, NP and NP-completeness / 2：

Variations on P and NP / 3：

More resources, more power? / 4：

Space complexity / 5：

Randomness and counting / 6：

続きを見る

東工大ブックレビュー

類似資料:

1 図書 Computational complexity : a conceptual perspective (: hbk) Goldreich, Oded Cambridge University Press	7 図書 The computational complexity of logical theories (: Berlin ; : New York) Ferrante, Jeanne, 1949-, Rackoff, Charles W., 1948- Springer-Verlag
2 電子ブック Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation Goldreich, Oded, Kanade, Takeo Springer eBooks Computer Science, Springer Berlin Heidelberg	8 図書 Computational complexity and natural language Barton, G. Edward, Berwick, Robert C., Ristad, Eric Sven MIT Press
3 電子ブック Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation Goldreich, Oded, Kanade, Takeo, Kittler, Josef SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg	9 図書 Computational complexity theory Hartmanis, Juris, American Mathematical Society, American Mathematical Society Short Course "Computational Complexity … American Mathematical Society
4 図書 Turing machines with sublogarithmic space (: gw ; : us) Szepietowski, Andrzej Springer-Verlag	10 図書 Randomness and completeness in computational complexity Melkebeek, Dieter van Springer-Verlag
5 図書 The annotated Turing : a guided tour through Alan Turing's historic paper on computability and the Turing Machine (pbk.) Petzold, Charles, 1953- Wiley Pub.	11 図書 Theories of computational complexity Calude, Cristian, 1952- North-Holland
6 図書 Computational complexity Papadimitriou, Christos H. Addison-Wesley	12 図書 Advances in computational complexity theory Cai, Jin-yi, 1961- American Mathematical Society