Computational Complexity

個数：

Computational Complexity

  • 在庫がございません。海外の書籍取次会社を通じて出版社等からお取り寄せいたします。
    通常6～9週間ほどで発送の見込みですが、商品によってはさらに時間がかかることもございます。
    【重要ご説明事項】
    1. 納期遅延や、ご入手不能となる場合がございます。
    2. 複数冊ご注文の場合、分割発送となる場合がございます。
    3. 美品のご指定は承りかねます。
  • 【入荷遅延について】
    世界情勢の影響により、海外からお取り寄せとなる洋書・洋古書の入荷が、表示している標準的な納期よりも遅延する場合がございます。
    おそれいりますが、あらかじめご了承くださいますようお願い申し上げます。
  • ◆画像の表紙や帯等は実物とは異なる場合があります。
  • ◆ウェブストアでの洋書販売価格は、弊社店舗等での販売価格とは異なります。
    また、洋書販売価格は、ご注文確定時点での日本円価格となります。
    ご注文確定後に、同じ洋書の販売価格が変動しても、それは反映されません。
  • 製本 Paperback:紙装版/ペーパーバック版／ページ数 544 p.
  • 言語 ENG
  • 商品コード 9780201530827
  • DDC分類 519.4

基本説明

Offers a comprehensive and accessible treatment of the theory of algorithms and complexity. Develops all the necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics, and probability. DLC: Computational complexity.

Full Description

This text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, parallel computation, the polynomial hierarchy, and many others. Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics and probability.

Contents

I. ALGORITHMS.

 1. Problems and Algorithms.
 2. Turing Machines.
 3. Undecidability.
II. LOGIC.

 1. Boolean Logic.
 2. First Order Logic.
 3. Undecidability in Logic.
III. P AND NP.

 1. Relations between Complexity Classes.
 2. Reductions and Completeness.
 3. NP-Complete Problems.
 4. coNP and Function Problems.
 5. Randomized Computation.
 6. Cryptography.
 7. Approximability.
 8. On P vs. NP.
IV. INSIDE P.

 1. Parallel Computation.
 2. Logarithmic Space.
V. BEYOND NP.

 1. The Polynomial Hierarchy.
 2. Computation That Counts.
 3. Polynomial Space.
 4. A Glimpse Beyond. 0201530821T04062001