商品詳細(参照) | Knowledge Worker

Computational Complexity. hardcover 500 p. 93

Papadimitriou, C.H. 　著

絶版
価格 \-

発行年月	1993年11月
出版社／提供元	Pearson Education (PH USA)
出版国	アメリカ合衆国
言語	英語
媒体	冊子
装丁	paper
ページ数／巻数	544 p.
ジャンル	洋書／理工学／情報科学／情報科学基礎
ISBN	9780201530827
商品コード	0209337599
本の性格	テキスト
商品URL	https://kw.maruzen.co.jp/ims/itemDetail.html?itmCd=0209337599

内容

Offers a comprehensive treatment of the theory of algorithms andcomplexity. Among topics covered are: reductions and NP - completeness,cryptography and protocols, randomized algorithms, and approximability ofoptimization problems, circuit complexity, the "structural" aspects of theP=NP question, parallel computation, and more.

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 ComplexityClasses. 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. ParallelComputation. 2. Logarithmic Space. V. BEYOND NP. 1. The PolynomialHierarchy. 2. Computation That Counts. 3. Polynomial Space. 4. AGlimpse Beyond. 0201530821T04062001