By Ding-Zhu Du, Ker-I Ko
"Complexity idea stories the inherent problems of fixing algorithmic difficulties by way of electronic pcs. This finished paintings discusses the foremost subject matters in complexity thought, together with primary themes in addition to fresh breakthroughs no longer formerly to be had in publication form."--BOOK JACKET. half I Uniform Complexity 1 -- 1 types of Computation and Complexity periods three -- 1.1 Strings, Coding, and Boolean services three -- 1.2 Deterministic Turing Machines 7 -- 1.3 Nondeterministic Turing Machines 14 -- 1.4 Complexity sessions 18 -- 1.5 common Turing laptop 24 -- 1.6 Diagonalization 27 -- 1.7 Simulation 31 -- 2 NP-Completeness forty three -- 2.1 NP forty three -- 2.2 Cook's Theorem forty seven -- 2.3 extra NP-Complete difficulties fifty one -- 2.4 Polynomial-Time Turing Reducibility fifty eight -- 2.5 NP-Complete Optimization difficulties sixty four -- three Polynomial-Time Hierarchy and Polynomial house seventy seven -- 3.1 Nondeterministic Oracle Turing Machines seventy seven -- 3.2 Polynomial-Time Hierarchy seventy nine -- 3.3 whole difficulties in PH eighty four -- 3.4 Alternating Turing Machines ninety -- 3.5 PSPACE-Complete difficulties ninety five -- 3.6 EXP-Complete difficulties 102 -- four constitution of NP 113 -- 4.1 Incomplete difficulties in NP 113 -- 4.2 One-Way features and Cryptography 119 -- 4.3 Relativization a hundred twenty five -- 4.4 Unrelativizable evidence recommendations 127 -- 4.5 Independence effects 127 -- 4.6 confident Relativization 129 -- 4.7 Random Oracles 131 -- 4.8 constitution of Relativized NP one hundred thirty five -- half II Nonuniform Complexity a hundred forty five -- five determination timber 147 -- 5.1 Graphs and choice bushes 147 -- 5.3 Algebraic Criterion 157 -- 5.4 Monotone Graph homes 161 -- 5.5 Topological Criterion 163 -- 5.6 purposes of the mounted element Theorems a hundred and seventy -- 5.7 purposes of Permutation teams 173 -- 5.8 Randomized determination timber 176 -- 5.9 Branching courses 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 functionality 221 -- 6.7 P-Completeness 229 -- 6.8 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 units 254 -- 7.4 Density of EXP-Complete units 262 -- 7.5 One-Way features and Isomorphism in EXP 266 -- 7.6 Density of P-Complete units 276 -- half III Probabilistic Complexity 285 -- eight Probabilistic Machines and Complexity periods 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 error 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 sessions 310 -- nine Complexity of Counting 321 -- 9.1 Counting category #P 322 -- 9.2 #P-Complete difficulties 325 -- 9.3 [plus check 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 up circle]P and #P 342 -- 9.6 Relativized Polynomial-Time Hierarchy 346 -- 10 Interactive facts structures 353 -- 10.2 Arthur-Merlin facts structures 361 -- 10.3 AM Hierarchy as opposed to Polynomial-Time Hierarchy 365 -- 10.4 IP as opposed to AM 372 -- 10.5 IP as opposed to PSPACE 382 -- eleven Probabilistically Checkable Proofs and NP-Hard Optimization difficulties 393 -- 11.1 Probabilistically Checkable Proofs 393 -- 11.2 PCP Characterization of Nondeterministic Exponential Time 396 -- 11.2.1 evidence 397 -- 11.2.2 Multilinearity attempt approach 403 -- 11.2.3 Sum fee procedure 408 -- 11.3 PCP Characterization of NP 410 -- 11.3.1 facts method for NP utilizing O(log n) Random Bits 412 -- 11.3.2 Low-Degree try procedure 416 -- 11.3.3 Composition of 2 PCP platforms 419 -- 11.3.4 facts procedure studying a relentless variety of Oracle Bits 424 -- 11.4 Probabilistic Checking and Nonapproximability 430 -- 11.5 extra NP-Hard Approximation difficulties 434
Read or Download Theory of Computational Complexity PDF
Similar discrete mathematics books
Computational Complexity of Sequential and Parallel Algorithms
This e-book provides a compact but accomplished survey of significant ends up in the computational complexity of sequential algorithms. this can be through a hugely informative creation to the improvement of parallel algorithms, with the emphasis on non-numerical algorithms. the fabric is so chosen that the reader in lots of situations is ready to stick to an identical challenge for which either sequential and parallel algorithms are mentioned - the simultaneous presentation of sequential and parallel algorithms for fixing permitting the reader to recognize their universal and specified positive aspects.
Discontinuum Mechanics : Using Finite and Discrete Elements
Textbook introducing the mathematical and computational ideas of touch mechanics that are used more and more in business and educational software of the mixed finite/discrete aspect procedure.
Matroids: A Geometric Introduction
Matroid thought is a colourful quarter of study that offers a unified method to comprehend graph conception, linear algebra and combinatorics through finite geometry. This e-book offers the 1st finished advent to the sphere in order to attract undergraduate scholars and to any mathematician attracted to the geometric method of matroids.
Fragile networks: Identifying Vulnerabilities and Synergies in an Uncertain World
A unified remedy of the vulnerabilities that exist in real-world community systems-with instruments to spot synergies for mergers and acquisitions Fragile Networks: opting for Vulnerabilities and Synergies in an doubtful international offers a complete examine of community structures and the jobs those structures play in our daily lives.
Additional resources for Theory of Computational Complexity
Example text
Therefore, for n = i + j we find i+ j ci+ j = ∑ ak bi+ j−k = ai b j . k=0 Since both ai and b j are nonzero, so is ci+ j , and therefore c(x) cannot be the zero series. n k If a(x) = ∑∞ n=0 an x is a formal power series, we will use the notation [x ]a(x) := ak k k to refer the coefficient of x . For fixed k ∈ , coefficient extraction [x ] : [[x]] → is a linear map. For k = 0, also the notations a(x)|x=0 := a(0) := [x0 ]a(x) are used. The coefficient of x0 is called the constant term of a(x). The definition of the Cauchy product may seem somewhat unmotivated at first sight, but there is a natural combinatorial interpretation for it.
1. For the moment, we record ∞ 1 n n k = ∑ x y 1 − x − xy n,k=0 k as its bivariate generating function. Like in the univariate case, operations on multivariate power series correspond to operations on the (multivariate) coefficient sequence. For example, multiplication by x corresponds to a shift in n and multiplication by y corresponds to shift in k. Our result about the bivariate generating function of the binomial coefficients is therefore just a reformulation of the Pascal triangle relation: (1 − x − xy) ∞ ∑ n,k=0 n n k x y =1 k =⇒ n n−1 n−1 − − = 0 (n, k > 0).
In that case we write a(x) = limk→∞ ak (x), a notation which is justified because the limit of a convergent sequence of power series is unique. ∞ n n If ak (x) = ∑∞ n=0 an,k x and a(x) = ∑n=0 an x , then convergence of the sequence ∞ (ak (x))k=0 to a(x) means that every coefficient sequence an,0 , an,1 , an,2 , an,3 , . . differs from an only for finitely many indices. 5 Let (an (x))∞ n=0 and (bn (x))n=0 be two convergent sequences in and let a(x) = limn→∞ an (x) and b(x) = limn→∞ bn (x). Then: Ã[[x]] 1.