Kooperativer Bibliotheksverbund

UID:

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

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

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

Content: "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.

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

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

Language: English

Subjects: Computer Science

Keywords: Electronic books. ; Electronic books.

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

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