Ding-Zhu Du, Ker-I Ko

Theory of Computational Complexity (eBook, ePUB)

• Format: ePub

Produktbeschreibung

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 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 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 science * Additional exercises at varying levels of difficulty to further test comprehension of the presented material * End-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.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: John Wiley & Sons
• Seitenzahl: 512
• Erscheinungstermin: 18. Juli 2014
• Englisch
• ISBN-13: 9781118594971
• Artikelnr.: 41209136

Autorenporträt

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.

Inhaltsangabe

Preface ix Notes on the Second Edition xv Part I Uniform Complexity 1 1
Models of Computation and Complexity Classes 3 1.1 Strings, Coding, and
Boolean Functions 3 1.2 Deterministic Turing Machines 7 1.3
Nondeterministic Turing Machines 14 1.4 Complexity Classes 17 1.5 Universal
Turing Machine 23 1.6 Diagonalization 27 1.7 Simulation 31 Exercises 35
Historical Notes 41 2 NP-Completeness 43 2.1 NP 43 2.2 Cook's Theorem 47
2.3 More NP-Complete Problems 51 2.4 Polynomial-Time Turing Reducibility 58
2.5 NP-Complete Optimization Problems 64 Exercises 71 Historical Notes 75 3
The Polynomial-Time Hierarchy and Polynomial Space 77 3.1 Nondeterministic
Oracle Turing Machines 77 3.2 Polynomial-Time Hierarchy 79 3.3 Complete
Problems in PH 84 3.4 Alternating Turing Machines 90 3.5 PSPACE-Complete
Problems 95 3.6 EXP-Complete Problems 102 Exercises 108 Historical Notes
111 4 Structure of NP 113 4.1 Incomplete Problems in NP 113 4.2 One-Way
Functions and Cryptography 116 4.3 Relativization 122 4.4 Unrelativizable
Proof Techniques 124 4.5 Independence Results 125 4.6 Positive
Relativization 126 4.7 Random Oracles 128 4.8 Structure of Relativized NP
132 Exercises 137 Historical Notes 140 Part II Nonuniform Complexity 141 5
Decision Trees 143 5.1 Graphs and Decision Trees 143 5.2 Examples 149 5.3
Algebraic Criterion 153 5.4 Monotone Graph Properties 157 5.5 Topological
Criterion 159 5.6 Applications of the Fixed Point Theorems 166 5.7
Applications of Permutation Groups 169 5.8 Randomized Decision Trees 172
5.9 Branching Programs 177 Exercises 184 Historical Notes 188 6 Circuit
Complexity 191 6.1 Boolean Circuits 191 6.2 Polynomial-Size Circuits 195
6.3 Monotone Circuits 201 6.4 Circuits with Modulo Gates 208 6.5 NC 212 6.6
Parity Function 217 6.7 P-Completeness 224 6.8 Random Circuits and RNC 230
Exercises 234 Historical Notes 237 7 Polynomial-Time Isomorphism 241 7.1
Polynomial-Time Isomorphism 241 7.2 Paddability 245 7.3 Density of
NP-Complete Sets 250 7.4 Density of EXP-Complete Sets 258 7.5 One-Way
Functions and Isomorphism in EXP 262 7.6 Density of P-Complete Sets 272
Exercises 275 Historical Notes 278 Part III Probabilistic Complexity 281 8
Probabilistic Machines and Complexity Classes 283 8.1 Randomized Algorithms
283 8.2 Probabilistic Turing Machines 288 8.3 Time Complexity of
Probabilistic Turing Machines 291 8.4 Probabilistic Machines with Bounded
Errors 294 8.5 BPP and P 297 8.6 BPP and NP 300 8.7 BPP and the
Polynomial-Time Hierarchy 302 8.8 Relativized Probabilistic Complexity
Classes 306 Exercises 311 Historical Notes 314 9 Complexity of Counting 317
9.1 Counting Class #P 318 9.2 #P-Complete Problems 321 9.3 oplus P and the
Polynomial-Time Hierarchy 330 9.4 #P and the Polynomial-Time Hierarchy 336
9.5 Circuit Complexity and Relativized oplus P and #P 338 9.6 Relativized
Polynomial-Time Hierarchy 342 Exercises 344 Historical Notes 347 10
Interactive Proof Systems 349 10.1 Examples and Definitions 349 10.2
Arthur-Merlin Proof Systems 357 10.3 AM Hierarchy Versus Polynomial-Time
Hierarchy 361 10.4 IP Versus AM 368 10.5 IP Versus PSPACE 378 Exercises 383
Historical Notes 386 11 Probabilistically Checkable Proofs and NP-Hard
Optimization Problems 389 11.1 Probabilistically Checkable Proofs 389 11.2
PCP Characterization of NP 392 11.2.1 Expanders 396 11.2.2 Gap
Amplification 399 11.2.3 Assignment Testers 410 11.4 Probabilistic Checking
and Inapproximability 418 11.5 More NP-Hard Approximation Problems 421
Exercises 432 Historical Notes 435 Bibliography 439 Index 461