內容簡介
《計算復雜性的現代方法》是一部將所有有關復雜度知識理論集於一體的教程。將最新進展和經典結果結閤起來,是一部很難得的研究生入門級教程。既是相關科研人員的一部很好的參考書,也是自學人員很難得的一本很好自學教程。本書一開始引入該領域的最基本知識,然後逐步深入,介紹更多深層次的結果,每章末都附有練習。對復雜度感興趣的人士,物理學傢,數學傢以及科研人員這本書都是相當受益。
目錄
About this bOok
Acknowledgments
Introduction
0 Notational conventions
PARTONE: BASIC COMPLEXITY CLASSES
1 The computational model--and why it doesn't matter
2 NP and NP completeness
3 Diagonalization
4 Space complexity
5 The polynomial hierarchy and alternations
6 Boolean circuits
7 Randomized computation
8 Interactive proofs
9 Cryptography
10 Quantum computation
11 PCP theorem and hardness of approximation: An introduction
PART TWO: LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS
12 Decision trees
13 Communication complexity
14 Circuit lower bounds: Complexity theory's Waterloo
15 Proof complexity
16 Algebraic computation models
PART THREE: ADVANCED TOPICS
17 Complexity of counting
18 Average case complexity: Levin's theory
19 Hardness amplification and error-correcting codes
20 Derandomization
21 Pseudorandom constructions: Expanders and extractors
22 Proofs of PCP theorems and the Fourier transform technique
23 Why are circuit lower bounds so difficult?
Appendix: Mathematical background
Hints and selected exercises
Main theorems and definitions
Bibliography
Index
Complexity class index
前言/序言
計算復雜性的現代方法 [Computational Complexity] 下載 mobi epub pdf txt 電子書 格式
評分
☆☆☆☆☆
知識是人類在實踐中認識客觀世界的成果。它可能包括事實,信息,描述或在教育和實踐中獲得的技能。它可能是關於理論的,也可能是關於實踐的。在哲學中,關於知識的研究叫做認識論。知識的獲取涉及到許多復雜的過程:感覺,交流,推理。知識也可以看成構成人類智慧的最根本的因素。
評分
☆☆☆☆☆
幫彆人買的,應該還不錯
評分
☆☆☆☆☆
是一本非常好的計算復雜性的入門書、進階書、參考書。
評分
☆☆☆☆☆
計算理論方麵的一本好書,用現代方法處理經典內容
評分
☆☆☆☆☆
開始一看感覺質量很差,最後發現是影印版,頓悟
評分
☆☆☆☆☆
介紹計算復雜性比較全的書。知識點比價全!
評分
☆☆☆☆☆
牛人arora的書,買來仰幕一下。
評分
☆☆☆☆☆
牛人arora的書,買來仰幕一下。
評分
☆☆☆☆☆
送貨速度非常快!送貨速度非常快!