復(fù)雜性理論

內(nèi)容概要

復(fù)雜性理論主要研究決定解決算法問題的必要資源，以及利用可用資源可能得到的結(jié)果的界，而對這些界的深入理解可以防止尋求不存在的所謂有效算法。復(fù)雜性理論的新分支隨著新的算法概念而不斷涌現(xiàn)，其產(chǎn)物——如NP一完備性理論——已經(jīng)影響到計算機(jī)科學(xué)的所有領(lǐng)域的發(fā)展。本書視隨機(jī)化為一個關(guān)鍵概念，強(qiáng)調(diào)理論與實際應(yīng)用的相互作用。本書論題始終強(qiáng)調(diào)復(fù)雜性理論對于當(dāng)今計算機(jī)科學(xué)的重要意義，包含各種具體應(yīng)用。

書籍目錄

1 Introduction  1.1 What Is Complexity Theory?  1.2 Didactic Background  1.3 Overview  1.4 Additional Literature2 Algorithmic Problems & Their Complexity  2.1 What Are Algorithmic Problems?  2.2 Some Important Algorithmic Problems  2.3 Measuring Computation Time   2.4 The Complexity of Algorithmic Problems3 Fundamental Complexity Classes  3.1 The Special Role of Polynomial Computation Time  3.2 Randomized Agorithms  3.3 The Fundamental Complexity Classes for Algorithmic Problems  3.4 The Fundamental Complexity Classes for Decision Problems  3.5 Nondeterminism as a Special Case of Randomization4 Reductions-Algorithmic Relationships Between Problems  4.1 When Are Two Problems Algorithmically Similar?  4.2 Reductions Between Various Vaariants of a Problem  4.3 Reductions Between Related Problems  4.4 Reductions Between Unrelated Problems  4.5 The Special Role of Polynomial Reductions5 The Theory of NP-Completeness  5.1 Fundamental Considerations  5.2 Problems in NP  5.3 Alternative Characterizations of NP  5.4 Cook s Theorem6 NP-complete and NP-equivalent Problems  6.1 Fundamental Considerations  6.2 Traveling Salesperson Problems  6.3 Knapsack Problems  6.4 Partitioning and Scheduling Problems  6.5 Clique Problems  6.6 Team Building Problems  6.7 Championship Problems7 The Complexity Analysis of Problems  7.1 The dividing Line Between Easy and Hard  7.2 Pseudo-polynomial Algorithms and Strong NP-comleteness  7.3 An Overview of the NP-competeness Proofs Considered8 The Complexity of Approximation Problems-Classical Results  8.1 Complexity Classes  8.2 Approximation Algorithms  8.3 The Gap Technique  8.4 Approximation-Preserving Reductions  8.5 Complete Approximation Problems9 The Complexity of Black Box Problems  9.1 Black Box Optimization  9.2 Yao s Minimax Principle  9.3 Lower Bounds for Black Box COmplexity10 Additional Complexity Classes11 Interactive Proofs12 The PCP Theorem and the Complexity of Approximation Problems13 Further Topics From Classical Complexity Theory14 The Complexity of Non-uniform Problems15 Communication Complexity16 The Complexity of Boolean FunctionsFinal CommentsA Appendix  A.1 Orders of Magnitude and O-Notation  A.2 Results from Probability TheoryReferencesIndex

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    復(fù)雜性理論 PDF格式下載

---