Average-Case Complexity

Andrej Bogdanov, Luca Trevisan (Autoren)

Buch | Softcover

120 Seiten

2006
now publishers Inc (Verlag)
978-1-933019-49-9 (ISBN)

Artikel merken

Offers a thorough survey of the average-case complexity of problems in NP. This survey examines the current state of knowledge on average-case complexity. The reader will also discover a number of results, insights, and proof techniques whose usefulness goes beyond the study of average-case complexity.

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

Reihe/Serie	Foundations and Trends® in Theoretical Computer Science
Verlagsort	Hanover
Sprache	englisch
Maße	156 x 234 mm
Gewicht	181 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
ISBN-10	1-933019-49-2 / 1933019492
ISBN-13	978-1-933019-49-9 / 9781933019499
Zustand	Neuware