Average-case complexity
著者
書誌事項
Average-case complexity
（Foundations and trends in theoretical computer science, 2:1）
now Publishers, c2006
- タイトル別名
-
Average case complexity
大学図書館所蔵 件 / 全7件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
"The preferred citation for this publication is ... Foundation and Trends [R] in Theoretical Computer Science, vol 2, no 1, pp 1-106, 2006"-T. p. verso
Bibliography: p. 107-111
内容説明・目次
内容説明
Average-Case Complexity is a thorough survey of the average-case complexity of problems in NP. The study of the average-case complexity of intractable problems began in the 1970s, motivated by two distinct applications: the developments of the foundations of cryptography and the search for methods to ""cope"" with the intractability of NP-hard problems.
This survey looks at both, and generally examines the current state of knowledge on average-case complexity. The book is intended for scholars and graduate students in the field of theoretical computer science. The reader will also discover a number of results, insights, and proof techniques whose usefulness goes beyond the study of average-case complexity.
目次
- 1. Introduction
- 2. Definitions of "Efficient on Average"
- 3. A Complete Problem for Computable Ensembles
- 4. Decision versus Search and One-Way Functions
- 5. Samplable Ensembles
- 6. Hardness Amplification
- 7. Worst-Case versus Average-Case and
「Nielsen BookData」 より
