Harvard |

Harvard

Matches in Harvard for { <http://id.lib.harvard.edu/aleph/008290460/catalog> ?p ?o. }

Showing items 1 to 33 of 33 with 100 items per page.

catalog abstract ""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.".
catalog contributor b11536794.
catalog contributor b11536795.
catalog created "c2000.".
catalog date "2000".
catalog date "c2000.".
catalog dateCopyrighted "c2000.".
catalog description ""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.".
catalog description "4.2 One-Way Functions and Cryptography 119 -- 4.3 Relativization 125 -- 4.4 Unrelativizable Proof Techniques 127 -- 4.5 Independence Results 127 -- 4.6 Positive Relativization 129 -- 4.7 Random Oracles 131 -- 4.8 Structure of Relativized NP 135 -- Part II Nonuniform Complexity 145 -- 5 Decision Trees 147 -- 5.1 Graphs and Decision Trees 147 -- 5.3 Algebraic Criterion 157 -- 5.4 Monotone Graph Properties 161 -- 5.5 Topological Criterion 163 -- 5.6 Applications of the Fixed Point Theorems 170 -- 5.7 Applications of Permutation Groups 173 -- 5.8 Randomized Decision Trees 176 -- 5.9 Branching Programs 181 -- 6 Circuit Complexity 195 -- 6.1 Boolean Circuits 195 -- 6.2 Polynomial-Size Circuits 199 -- 6.3 Monotone Circuits 205 -- 6.4 Circuits with Modulo Gates 213 -- 6.5 NC 216 -- 6.6 Parity Function 221 -- 6.7 P-Completeness 229 -- 6.8".
catalog description "419 -- 11.3.4 Proof System Reading a Constant Number of Oracle Bits 424 -- 11.4 Probabilistic Checking and Nonapproximability 430 -- 11.5 More NP-Hard Approximation Problems 434.".
catalog description "Includes bibliographical references (p. 453-473) and index.".
catalog description "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 18 -- 1.5 Universal Turing Machine 24 -- 1.6 Diagonalization 27 -- 1.7 Simulation 31 -- 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 -- 3 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 -- 4 Structure of NP 113 -- 4.1 Incomplete Problems in NP 113 --".
catalog description "Random Circuits and RNC 234 -- 7 Polynomial-Time Isomorphism 245 -- 7.1 Polynomial-Time Isomorphism 245 -- 7.2 Paddability 249 -- 7.3 Density of NP-Complete Sets 254 -- 7.4 Density of EXP-Complete Sets 262 -- 7.5 One-Way Functions and Isomorphism in EXP 266 -- 7.6 Density of P-Complete Sets 276 -- Part III Probabilistic Complexity 285 -- 8 Probabilistic Machines and Complexity Classes 287 -- 8.1 Randomized Algorithms 287 -- 8.2 Probabilistic Turing Machines 292 -- 8.3 Time Complexity of Probabilistic Turing Machines 295 -- 8.4 Probabilistic Machines with Bounded Errors 298 -- 8.5 BPP and P 301 -- 8.6 BPP and NP 304 -- 8.7 BPP and the Polynomial-Time Hierarchy 306 -- 8.8 Relativized Probabilistic Complexity Classes 310 -- 9 Complexity of Counting 321 -- 9.1 Counting Class #P 322 -- 9.2 #P-Complete Problems 325 -- 9.3".
catalog description "[plus sign in circle]P and the Polynomial-Time Hierarchy 334 -- 9.4 #P and the Polynomial-Time Hierarchy 340 -- 9.5 Circuit Complexity and Relativized [plus sign in circle]P and #P 342 -- 9.6 Relativized Polynomial-Time Hierarchy 346 -- 10 Interactive Proof Systems 353 -- 10.2 Arthur-Merlin Proof Systems 361 -- 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 365 -- 10.4 IP Versus AM 372 -- 10.5 IP Versus PSPACE 382 -- 11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 393 -- 11.1 Probabilistically Checkable Proofs 393 -- 11.2 PCP Characterization of Nondeterministic Exponential Time 396 -- 11.2.1 Proof 397 -- 11.2.2 Multilinearity Test System 403 -- 11.2.3 Sum Check System 408 -- 11.3 PCP Characterization of NP 410 -- 11.3.1 Proof System for NP Using O(log n) Random Bits 412 -- 11.3.2 Low-Degree Test System 416 -- 11.3.3 Composition of Two PCP Systems".
catalog extent "xiii, 491 p. :".
catalog hasFormat "Theory of computational complexity.".
catalog identifier "0471345067 (alk. paper)".
catalog isFormatOf "Theory of computational complexity.".
catalog issued "2000".
catalog issued "c2000.".
catalog language "eng".
catalog publisher "New York : Wiley-Interscience,".
catalog relation "Theory of computational complexity.".
catalog subject "511.3 21".
catalog subject "Computational complexity.".
catalog subject "QA267.7 .D8 2000".
catalog tableOfContents "4.2 One-Way Functions and Cryptography 119 -- 4.3 Relativization 125 -- 4.4 Unrelativizable Proof Techniques 127 -- 4.5 Independence Results 127 -- 4.6 Positive Relativization 129 -- 4.7 Random Oracles 131 -- 4.8 Structure of Relativized NP 135 -- Part II Nonuniform Complexity 145 -- 5 Decision Trees 147 -- 5.1 Graphs and Decision Trees 147 -- 5.3 Algebraic Criterion 157 -- 5.4 Monotone Graph Properties 161 -- 5.5 Topological Criterion 163 -- 5.6 Applications of the Fixed Point Theorems 170 -- 5.7 Applications of Permutation Groups 173 -- 5.8 Randomized Decision Trees 176 -- 5.9 Branching Programs 181 -- 6 Circuit Complexity 195 -- 6.1 Boolean Circuits 195 -- 6.2 Polynomial-Size Circuits 199 -- 6.3 Monotone Circuits 205 -- 6.4 Circuits with Modulo Gates 213 -- 6.5 NC 216 -- 6.6 Parity Function 221 -- 6.7 P-Completeness 229 -- 6.8".
catalog tableOfContents "419 -- 11.3.4 Proof System Reading a Constant Number of Oracle Bits 424 -- 11.4 Probabilistic Checking and Nonapproximability 430 -- 11.5 More NP-Hard Approximation Problems 434.".
catalog tableOfContents "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 18 -- 1.5 Universal Turing Machine 24 -- 1.6 Diagonalization 27 -- 1.7 Simulation 31 -- 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 -- 3 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 -- 4 Structure of NP 113 -- 4.1 Incomplete Problems in NP 113 --".
catalog tableOfContents "Random Circuits and RNC 234 -- 7 Polynomial-Time Isomorphism 245 -- 7.1 Polynomial-Time Isomorphism 245 -- 7.2 Paddability 249 -- 7.3 Density of NP-Complete Sets 254 -- 7.4 Density of EXP-Complete Sets 262 -- 7.5 One-Way Functions and Isomorphism in EXP 266 -- 7.6 Density of P-Complete Sets 276 -- Part III Probabilistic Complexity 285 -- 8 Probabilistic Machines and Complexity Classes 287 -- 8.1 Randomized Algorithms 287 -- 8.2 Probabilistic Turing Machines 292 -- 8.3 Time Complexity of Probabilistic Turing Machines 295 -- 8.4 Probabilistic Machines with Bounded Errors 298 -- 8.5 BPP and P 301 -- 8.6 BPP and NP 304 -- 8.7 BPP and the Polynomial-Time Hierarchy 306 -- 8.8 Relativized Probabilistic Complexity Classes 310 -- 9 Complexity of Counting 321 -- 9.1 Counting Class #P 322 -- 9.2 #P-Complete Problems 325 -- 9.3".
catalog tableOfContents "[plus sign in circle]P and the Polynomial-Time Hierarchy 334 -- 9.4 #P and the Polynomial-Time Hierarchy 340 -- 9.5 Circuit Complexity and Relativized [plus sign in circle]P and #P 342 -- 9.6 Relativized Polynomial-Time Hierarchy 346 -- 10 Interactive Proof Systems 353 -- 10.2 Arthur-Merlin Proof Systems 361 -- 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 365 -- 10.4 IP Versus AM 372 -- 10.5 IP Versus PSPACE 382 -- 11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 393 -- 11.1 Probabilistically Checkable Proofs 393 -- 11.2 PCP Characterization of Nondeterministic Exponential Time 396 -- 11.2.1 Proof 397 -- 11.2.2 Multilinearity Test System 403 -- 11.2.3 Sum Check System 408 -- 11.3 PCP Characterization of NP 410 -- 11.3.1 Proof System for NP Using O(log n) Random Bits 412 -- 11.3.2 Low-Degree Test System 416 -- 11.3.3 Composition of Two PCP Systems".
catalog title "Theory of computational complexity / Ding-Zhu Du, Ker-I Ko.".
catalog type "text".