Average-Case Complexity
1st Edition
Published on 13. December 2006
Book
Paperback/Softback
120 pages
978-1-933019-49-9 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Hanover
United States
Target group
College/higher education
Professional and scholarly
Dimensions
Height: 234 mm
Width: 156 mm
Weight
181 gr
ISBN-13
978-1-933019-49-9 (9781933019499)
DOI
10.1561/0400000004
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
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