Buch, Englisch, Band 5, 120 Seiten, Format (B × H): 156 mm x 234 mm
Reihe: Foundations and Trends® in Theoretical Computer Science
Buch, Englisch, Band 5, 120 Seiten, Format (B × H): 156 mm x 234 mm
Reihe: Foundations and Trends® in Theoretical Computer Science
ISBN: 978-1-933019-49-9
Verlag: Now Publishers
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. Average-Case Complexity 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.
Weitere Infos & Material
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
