計算復(fù)雜性

內(nèi)容概要

　　計算復(fù)雜性理論的研究是計算機科學(xué)最重要的研究領(lǐng)域之一，而Christos H．Papadmitriou是該領(lǐng)域最著名的專家之一。本書是一本全面闡述計算復(fù)雜性理論及其近年來進(jìn)展的教科書，主要包含算法圖靈機、可計算性等有關(guān)計算復(fù)雜性理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等復(fù)雜性理論的基礎(chǔ)知識；P與NP、NP完全等各復(fù)雜性類的概念及其之間的關(guān)系等復(fù)雜性理論的核心內(nèi)容；隨機算法、近似算法、并行算法及其復(fù)雜性理論；以及NP之外如多項式空間等復(fù)雜性類的介紹?！　”緯鴥?nèi)容豐富，體系嚴(yán)謹(jǐn)，證明簡潔，敘述深入淺出，并配有大量的練習(xí)和文獻(xiàn)引用。本書不但適合作為研究生或本科高年級學(xué)生的教材，也適合從事算法和計算機復(fù)雜性研究的人員參考。

書籍目錄

PART I：ALGORITHMS1 Problems and Algorithms1.1 Graph reachability1.2 Maximum flow and matching1.3 The traveling salesman problem1.4 Notes，references，and problems2 Turing machines2.1 Turing machine basics2.2 Turing machines as algorithms2.3 Turing machines with multiple strings2.4 Linear speedup2.5 Space bounds2.6 Random access machines2.7 Nondeterministic machines2.8 Notes，references，and problems3 Undecidability3.1 Universal Turing machines3.2 The halting problem3.3 More undecidability3.4 Notes，references，and problemsPART II：LOGIC4 Boolean logic4.1 Boolean Expressions4.2 Satisfiability and validity4.3 Boolean functions and circuits4.4 Notes，references，and problems5 First-order logic5.1 The syntax of first-order logic5.2 Models5.3 Valid expressions5.4 Axioms and proofs5.5 The completeness theorem5.6 Consequences of the completeness theorem5.7 Second-order logic5.8 Notes，references，and problems6 Undecidability in logic6.1 Axioms for number theory6.2 Computation as a number-theoretic concept6.3 Undecidability and incompleteness6.4 Notes，references，and problemsPART III：P AND NP7 Relations between complexity classes7.1 Complexity classes7.2 The hierarchy theorem7.3 The reachability method7.4 Notes，references，and problems8 Reductions and completeness8.1 Reductions8.2 Completeness8.3 Logical characterizations8.4 Notes，referencess，and problems9 NP-complete problems9.1 Problems in NP9.2 Variants of satisfiability9.3 Graph-theoretic problems9.4 Sets and numbers9.5 Notes，references，and problems10 coNP and function problems10.1 NP and coNP10.2 Primality10.3 Function problems10.4 Notes，references，and problems11 Randomized computation11.1 Randomized algorithms11.2 Randomized complexity classes11.3 Random sources11.4 Circuit complexity11.5 Notes，references，and problems12 Cryptography12.1 One-way functions12.2 Protocols12.3 Notes，references，and problems13 Approximability13.1 Approximation algorithms13.2 Approximation and complexity13.3 Nonapproximability13.4 Notes，references，and problems14 On P vs.NP14.1 The map of NP14.2 Isomorphism and density14.3 Oracles14.4 Monotone circuits14.5 Notes，references，and problemsPART IV：INSIDE P15 Parallel computation15.1 Parallel algorithms15.2 Parallel models of computation15.3 The class NC15.4 RNC algorithms15.5 Notes，references，and problems16 Logarithmic space16.1 The L=NL problem16.2 Alternation16.3 Undirected reachability16.4 Notes，references，and problemsPART V：BEYOND NP17 The polynomial hierarchy17.1 Optimization problems17.2 The hierarchy17.3 Notes，references，and problems18 Computation that counts18.1 The permanent18.2 The Class P18.3 Notes，references，and problems19 Polynomial space19.1 Alternation and games19.2 Games against nature and interactive protocols19.3 More PSPACE-complete problems19.4 Notes，references，and problems20 A glimpse beyond20.1 Exponential time20.2 Notes，references，and problemsIndexAuthor index

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計算復(fù)雜性 PDF格式下載

---