Average-Case Complexity

Купить бумажную книгу и читать

Авторы: Andrej Bogdanov, Luca Trevisan

Название: Average-Case Complexity

Издательство: Now Publishers Inc.

ISBN: 1-933019-49-2

Год: 2006

Количество страниц: 122

Формат: PDF

Размер: 12 Mb

Язык: English

Для сайта:

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.