Del i serien Wiley Series in Discrete Mathematics and Optimization

Theory of Computational Complexity

Inbunden, Engelska, 2014

1 869 kr

Beställningsvara. Skickas inom 7-10 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

Praise 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 MATHA 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 software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered.Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer scienceAdditional exercises at varying levels of difficulty to further test comprehension of the presented materialEnd-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.

Produktinformation

Utgivningsdatum2014-07-11
Mått163 x 236 x 31 mm
Vikt839 g
FormatInbunden
SpråkEngelska
SerieWiley Series in Discrete Mathematics and Optimization
Antal sidor512
Upplaga2
FörlagJohn Wiley & Sons Inc
ISBN9781118306086

Tillhör följande kategorier

Matematikens grunder inom Naturvetenskap och teknik

DING-ZHU DU, PhD, is Professor in the Department of Computer Science at the University of Texas at Dallas. He has published over 180 journal articles in his areas of research interest, which include design and analysis of approximation algorithms for combinatorial optimization problems and communication networks. Dr. Du is also the coauthor of Problem Solving in Automata, Languages, and Complexity, also published by Wiley.KER-I KO, PhD, is Professor in the Department of Computer Science at National Chiao Tung University, Taiwan. He has published extensively in his areas of research interest, which include computational complexity theory and its applications to numerical computation. Dr. Ko is also the coauthor of Problem Solving in Automata, Languages, and Complexity, also published by Wiley.

Preface ixNotes on the Second Edition xvPart I Uniform Complexity 11 Models of Computation and Complexity Classes 31.1 Strings, Coding, and Boolean Functions 31.2 Deterministic Turing Machines 71.3 Nondeterministic Turing Machines 141.4 Complexity Classes 181.5 Universal Turing Machine 251.6 Diagonalization 291.7 Simulation 33Exercises 38Historical Notes 432 NP-Completeness 452.1 Np 452.2 Cook’s Theorem 492.3 More NP-Complete Problems 542.4 Polynomial-Time Turing Reducibility 612.5 NP-Complete Optimization Problems 68Exercises 76Historical Notes 793 The Polynomial-Time Hierarchy and Polynomial Space 813.1 Nondeterministic Oracle Turing Machines 813.2 Polynomial-Time Hierarchy 833.3 Complete Problems in PH 883.4 Alternating Turing Machines 953.5 PSPACE-Complete Problems 1003.6 EXP-Complete Problems 108Exercises 114Historical Notes 1174 Structure of NP 1194.1 Incomplete Problems in NP 1194.2 One-Way Functions and Cryptography 1224.3 Relativization 1294.4 Unrelativizable Proof Techniques 1314.5 Independence Results 1314.6 Positive Relativization 1324.7 Random Oracles 1354.8 Structure of Relativized NP 140Exercises 144Historical Notes 147Part II Nonuniform Complexity 1495 Decision Trees 1515.1 Graphs and Decision Trees 1515.2 Examples 1575.3 Algebraic Criterion 1615.4 Monotone Graph Properties 1665.5 Topological Criterion 1685.6 Applications of the Fixed Point Theorems 1755.7 Applications of Permutation Groups 1795.8 Randomized Decision Trees 1825.9 Branching Programs 187Exercises 194Historical Notes 1986 Circuit Complexity 2006.1 Boolean Circuits 2006.2 Polynomial-Size Circuits 2046.3 Monotone Circuits 2106.4 Circuits with Modulo Gates 2196.5 Nc 2226.6 Parity Function 2286.7 P-Completeness 2356.8 Random Circuits and RNC 242Exercises 246Historical Notes 2497 Polynomial-Time Isomorphism 2527.1 Polynomial-Time Isomorphism 2527.2 Paddability 2567.3 Density of NP-Complete Sets 2617.4 Density of EXP-Complete Sets 2717.5 One-Way Functions and Isomorphism in EXP 2757.6 Density of P-Complete Sets 285Exercises 289Historical Notes 292Part III Probabilistic Complexity 2958 Probabilistic Machines and Complexity Classes 2978.1 Randomized Algorithms 2978.2 Probabilistic Turing Machines 3028.3 Time Complexity of Probabilistic Turing Machines 3058.4 Probabilistic Machines with Bounded Errors 3098.5 BPP and P 3128.6 BPP and NP 3158.7 BPP and the Polynomial-Time Hierarchy 3188.8 Relativized Probabilistic Complexity Classes 321Exercises 327Historical Notes 3309 Complexity of Counting 3329.1 Counting Class #P 3339.2 #P-Complete Problems 3369.3 ⊕P and the Polynomial-Time Hierarchy 3469.4 #P and the Polynomial-Time Hierarchy 3529.5 Circuit Complexity and Relativized ⊕P and #P 3549.6 Relativized Polynomial-Time Hierarchy 358Exercises 361Historical Notes 36410 Interactive Proof Systems 36610.1 Examples and Definitions 36610.2 Arthur–Merlin Proof Systems 37510.3 AM Hierarchy Versus Polynomial-Time Hierarchy 37910.4 IP Versus AM 38710.5 IP Versus PSPACE 396Exercises 402Historical Notes 40611 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 40711.1 Probabilistically Checkable Proofs 40711.2 PCP Characterization of NP 41111.2.1 Expanders 41411.2.2 Gap Amplification 41811.2.3 Assignment Tester 42811.3 Probabilistic Checking and Inapproximability 43711.4 More NP-Hard Approximation Problems 440Exercises 452Historical Notes 455References 458Index 480