000 06835cam a2200865 i 4500
001 sulb-eb0032976
003 BD-SySUS
005 20170713221350.0
006 m o d
007 cr |||||||||||
008 131204s2014 nju ob 001 0 eng
010 _a 2013048402
040 _aDLC
_beng
_erda
_epn
_cDLC
_dBTCTA
_dCUS
_dOCLCF
_dEBLCP
_dYDXCP
_dN$T
_dDG1
_dE7B
_dCOO
_dUMI
_dDEBBG
_dDEBSZ
_dOCLCQ
_dBD-SySUS
019 _a880827316
_a890704289
_a908035677
_a961539877
_a962565147
020 _a9781118594971
_q(epub)
020 _a1118594975
_q(epub)
020 _a9781118593035
_q(pdf)
020 _a1118593030
_q(pdf)
020 _a9781118032916
_q(online)
020 _a1118032918
_q(online)
020 _a9781118595091
020 _a1118595092
020 _z9781118306086
_q(cloth)
020 _z0471345067
_q(print)
020 _z1118306082
029 1 _aAU@
_b000052313344
029 1 _aCHBIS
_b010259700
029 1 _aCHVBK
_b325941793
029 1 _aDEBBG
_bBV042182590
029 1 _aDEBSZ
_b417232748
029 1 _aNZ1
_b15592017
029 1 _aDEBBG
_bBV043396388
035 _a(OCoLC)864753086
_z(OCoLC)880827316
_z(OCoLC)890704289
_z(OCoLC)908035677
_z(OCoLC)961539877
_z(OCoLC)962565147
037 _aCL0500000480
_bSafari Books Online
042 _apcc
050 0 0 _aQA267.7
072 7 _aMAT
_x000000
_2bisacsh
082 0 0 _a511.3/52
_223
049 _aMAIN
100 1 _aDu, Dingzhu,
_eauthor.
245 1 0 _aTheory of computational complexity /
_cDing-Zhu Du, Department of Computer Science, University of Texas at Dallas, Ann Arbor, MI, Ker-I Ko, Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY.
250 _aSecond edition.
264 1 _aHoboken, New Jersey :
_bJohn Wiley & Sons,
_c2014.
300 _a1 online resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
490 1 _aWiley-Interscience series in discrete mathematics and optimization
504 _aIncludes bibliographical references and index.
588 0 _aPrint version record and CIP data provided by publisher.
505 0 _aCover; Title Page; Contents; Preface; Notes on the Second Edition; Part I Uniform Complexity; Chapter 1 Models of Computation and Complexity Classes; 1.1 Strings, Coding, and Boolean Functions; 1.2 Deterministic Turing Machines; 1.3 Nondeterministic Turing Machines; 1.4 Complexity Classes; 1.5 Universal Turing Machine; 1.6 Diagonalization; 1.7 Simulation; Exercises; Historical Notes; Chapter 2 NP-Completeness; 2.1 NP; 2.2 Cook's Theorem; 2.3 More NP-Complete Problems; 2.4 Polynomial-Time Turing Reducibility; 2.5 NP-Complete Optimization Problems; Exercises; Historical Notes.
505 8 _aChapter 3 The Polynomial-Time Hierarchy and Polynomial Space3.1 Nondeterministic Oracle Turing Machines; 3.2 Polynomial-Time Hierarchy; 3.3 Complete Problems in PH; 3.4 Alternating Turing Machines; 3.5 PSPACE-Complete Problems; 3.6 EXP-Complete Problems; Exercises; Historical Notes; Chapter 4 Structure of NP; 4.1 Incomplete Problems in NP; 4.2 One-Way Functions and Cryptography; 4.3 Relativization; 4.4 Unrelativizable Proof Techniques; 4.5 Independence Results; 4.6 Positive Relativization; 4.7 Random Oracles; 4.8 Structure of Relativized NP; Exercises; Historical Notes.
505 8 _aPart II Nonuniform ComplexityChapter 5 Decision Trees; 5.1 Graphs and Decision Trees; 5.2 Examples; 5.3 Algebraic Criterion; 5.4 Monotone Graph Properties; 5.5 Topological Criterion; 5.6 Applications of the Fixed Point Theorems; 5.7 Applications of Permutation Groups; 5.8 Randomized Decision Trees; 5.9 Branching Programs; Exercises; Historical Notes; Chapter 6 Circuit Complexity; 6.1 Boolean Circuits; 6.2 Polynomial-Size Circuits; 6.3 Monotone Circuits; 6.4 Circuits with Modulo Gates; 6.5 NC; 6.6 Parity Function; 6.7 P-Completeness; 6.8 Random Circuits and RNC; Exercises; Historical Notes.
505 8 _aChapter 7 Polynomial-Time Isomorphism7.1 Polynomial-Time Isomorphism; 7.2 Paddability; 7.3 Density of NP-Complete Sets; 7.4 Density of EXP-Complete Sets; 7.5 One-Way Functions and Isomorphism in EXP; 7.6 Density of P-Complete Sets; Exercises; Historical Notes; Part III Probabilistic Complexity; Chapter 8 Probabilistic Machines and Complexity Classes; 8.1 Randomized Algorithms; 8.2 Probabilistic Turing Machines; 8.3 Time Complexity of Probabilistic Turing Machines; 8.4 Probabilistic Machines with Bounded Errors; 8.5 BPP and P; 8.6 BPP and NP; 8.7 BPP and the Polynomial-Time Hierarchy.
505 8 _a8.8 Relativized Probabilistic Complexity ClassesExercises; Historical Notes; Chapter 9 Complexity of Counting; 9.1 Counting Class #P; 9.2 #P-Complete Problems; 9.3 oplus P and the Polynomial-Time Hierarchy; 9.4 #P and the Polynomial-Time Hierarchy; 9.5 Circuit Complexity and Relativized oplus P and #P; 9.6 Relativized Polynomial-Time Hierarchy; Exercises; Historical Notes; Chapter 10 Interactive Proof Systems; 10.1 Examples and Definitions; 10.2 Arthur-Merlin Proof Systems; 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy; 10.4 IP Versus AM; 10.5 IP Versus PSPACE; Exercises.
520 _aPraise for the First Edition "" ... complete, up-to-date coverage of computational complexity theory ... the book promises to become the standard reference on computational complexity.""--Zentralblatt MATH A thorough revision based on advances in the field of computational complexity and readers' feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of.
650 0 _aComputational complexity.
650 4 _aComputational complexity.
650 7 _aMATHEMATICS
_xGeneral.
_2bisacsh
650 7 _aComputational complexity.
_2fast
_0(OCoLC)fst00871991
650 7 _aComputational complexity.
_2local
655 4 _aElectronic books.
700 1 _aKo, Ker-I,
_eauthor.
776 0 8 _iPrint version:
_aDu, Dingzhu, author.
_tTheory of computational complexity.
_bSecond edition.
_dHoboken, New Jersey : John Wiley & Sons, Inc., 2014
_z9781118306086
_w(DLC) 2013047839
830 0 _aWiley-Interscience series in discrete mathematics and optimization.
856 4 0 _uhttp://onlinelibrary.wiley.com/book/10.1002/9781118595091
_zWiley Online Library [Free Download only for SUST IP]
938 _aBaker and Taylor
_bBTCP
_nBK0014181124
938 _aEBL - Ebook Library
_bEBLB
_nEBL1695068
938 _aebrary
_bEBRY
_nebr10876079
938 _aEBSCOhost
_bEBSC
_n784130
938 _aYBP Library Services
_bYANK
_n11828286
938 _aYBP Library Services
_bYANK
_n11072126
938 _aYBP Library Services
_bYANK
_n12672917
994 _a92
_bDG1
999 _c64628
_d64628