Average-Case Complexity (Foundations and Trends® in Theoretical Computer Science)

個数：

Average-Case Complexity (Foundations and Trends® in Theoretical Computer Science)

Bogdanov, Andrej/ Trevisan, Luca

ウェブストア価格 ¥18,923（本体¥17,203）
now publishers Inc（2006/12発売）
外貨定価 UK£ 66.50
ポイント 172pt

在庫がございません。海外の書籍取次会社を通じて出版社等からお取り寄せいたします。
通常6～9週間ほどで発送の見込みですが、商品によってはさらに時間がかかることもございます。
【重要ご説明事項】
1. 納期遅延や、ご入手不能となる場合がございます。
2. 複数冊ご注文の場合は、ご注文数量が揃ってからまとめて発送いたします。
3. 美品のご指定は承りかねます。

●3Dセキュア導入とクレジットカードによるお支払いについて

【入荷遅延について】
世界情勢の影響により、海外からお取り寄せとなる洋書・洋古書の入荷が、表示している標準的な納期よりも遅延する場合がございます。
おそれいりますが、あらかじめご了承くださいますようお願い申し上げます。

◆画像の表紙や帯等は実物とは異なる場合があります。

◆ウェブストアでの洋書販売価格は、弊社店舗等での販売価格とは異なります。
また、洋書販売価格は、ご注文確定時点での日本円価格となります。
ご注文確定後に、同じ洋書の販売価格が変動しても、それは反映されません。

製本 Paperback:紙装版/ペーパーバック版／ページ数 120 p.
言語 ENG
商品コード 9781933019499
DDC分類 511.3

Full 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. 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