Kooperativer Bibliotheksverbund

UID:

Umfang: 1 online resource

Ausgabe: Second edition.

ISBN: 9781118594971 , 1118594975 , 9781118593035 , 1118593030 , 9781118032916 , 1118032918 , 9781118595091 , 1118595092

Inhalt: 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.

Anmerkung: Cover; 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. , Chapter 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. , Part 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. , Chapter 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. , 8.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.

Weitere Ausg.: Print version: Du, Dingzhu. Theory of computational complexity. Hoboken, New Jersey : John Wiley & Sons, Inc., 2014 ISBN 9781118306086

Sprache: Englisch

Schlagwort(e): Electronic books. ; Electronic books. ; Electronic books. ; Electronic books. ; Electronic books. ; Electronic books.

URL: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118595091

URL: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118595091

URL: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118595091

UID:

Umfang: 1 online resource (xiii, 491 pages) : , illustrations

Ausgabe: Electronic reproduction. [Place of publication not identified] : HathiTrust Digital Library, 2010.

ISBN: 9781118031162 , 1118031164 , 9781118032916 , 1118032918 , 0471345067 , 9780471345060

Inhalt: "Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form."--Jacket.

Anmerkung: Uniform Complexity , Models of Computation and Complexity Classes , Strings, Coding, and Boolean Functions , Deterministic Turing Machines , Nondeterministic Turing Machines , Complexity Classes , Universal Turing Machine , Diagonalization , Simulation , NP-Completeness , NP , Cook's Theorem , More NP-Complete Problems , Polynomial-Time Turing Reducibility , NP-Complete Optimization Problems , Polynomial-Time Hierarchy and Polynomial Space , Nondeterministic Oracle Turing Machines , Polynomial-Time Hierarchy , Complete Problems in PH , Alternating Turing Machines , PSPACE-Complete Problems , EXP-Complete Problems , Structure of NP , Incomplete Problems in NP , One-Way Functions and Cryptography , Relativization , Unrelativizable Proof Techniques , Independence Results , Positive Relativization , Random Oracles , Structure of Relativized NP , Nonuniform Complexity , Decision Trees , Graphs and Decision Trees , Algebraic Criterion , Monotone Graph Properties , Topological Criterion , Applications of the Fixed Point Theorems , Applications of Permutation Groups , Randomized Decision Trees , Branching Programs , Circuit Complexity , Boolean Circuits , Polynomial-Size Circuits , Monotone Circuits , Circuits with Modulo Gates , NC , Parity Function , P-Completeness , Random Circuits and RNC , Polynomial-Time Isomorphism , Polynomial-Time Isomorphism , Paddability , Density of NP-Complete Sets , Density of EXP-Complete Sets , One-Way Functions and Isomorphism in EXP , Density of P-Complete Sets , Probabilistic Complexity , Probabilistic Machines and Complexity Classes , Randomized Algorithms , Probabilistic Turing Machines , Time Complexity of Probabilistic Turing Machines , Probabilistic Machines with Bounded Errors , BPP and P , BPP and NP , BPP and the Polynomial-Time Hierarchy , Relativized Probabilistic Complexity Classes , Complexity of Counting , Counting Class #P , #P-Complete Problems , [plus sign in circle]P and the Polynomial-Time Hierarchy , #P and the Polynomial-Time Hierarchy , Circuit Complexity and Relativized [plus sign in circle]P and #P , Relativized Polynomial-Time Hierarchy , Interactive Proof Systems , Arthur-Merlin Proof Systems , AM Hierarchy Versus Polynomial-Time Hierarchy , IP Versus AM , IP Versus PSPACE , Probabilistically Checkable Proofs and NP-Hard Optimization Problems , Probabilistically Checkable Proofs , PCP Characterization of Nondeterministic Exponential Time , Proof , Multilinearity Test System , Sum Check System , PCP Characterization of NP , Proof System for NP Using O(log n) Random Bits , Low-Degree Test System , Composition of Two PCP Systems , Proof System Reading a Constant Number of Oracle Bits , Probabilistic Checking and Nonapproximability , More NP-Hard Approximation Problems , Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002.

Weitere Ausg.: Print version: Du, Dingzhu. Theory of computational complexity. New York : Wiley, ©2000 ISBN 0471345067

Sprache: Englisch

Fachgebiete: Informatik

Schlagwort(e): Electronic books. ; Electronic books.

URL: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118032916

URL: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118032916