Computational Complexity

Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.

Type

Book

Intellectual base

Review or monograph

Year

2009

DOI

10.1017/cbo9780511804090

ISBN

9780521424264

DOI registrant

Cambridge University Press

Link

https://doi.org/10.1017/CBO9780511804090

Cited from

computer_science

Cited by

8 citations across 8 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Complexity (Time/Space)
  • The constant factors and lower bounds (Ω) versus upper bounds (O) bounding the feasible region

    This sourceGraduate text covering complexity classes, lower vs. upper bounds, and cryptographic hardness assumptions (factoring, discrete log, lattice problems conjectured exponential-time) — supports D30-140 and D30-149. Verified existing and supporting.

    Supported in partVerified against the publisher's abstract

    The abstract places the topic in the book's scope (time/space complexity classes, lower bounds for concrete models) but never states the claim's constant-factor, Ω-versus-O, feasible-region proposition.

    “Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom …”

    Read by an automated reader; not a human review. How support was checked

Domain-specific

• AC (complexity)
  • AC^i contains languages recognized by polynomial-size circuit families of depth O(log^i n) using NOT and unbounded-fan-in AND and OR gates, under a stated uniformity convention.
• Approximation Algorithm
  • Thus the field manages both constructive choices and limits on what efficient computation can guarantee.
• Big O Notation
  • The notation is also the foundation of computational complexity theory, where complexity classes (P, NP, PSPACE, EXPTIME) are defined by the asymptotic resource bounds their problems respect, and deciding the relationships among those classes is the central open problem of the field

    This sourceGraduate textbook presenting computational complexity theory from the definition of time and space complexity classes to the classical and recent results of the field.

    Supported in partVerified against the work's full text

    “definition of Turing machines and basic time and space complexity classes”

    Read by an automated reader; not a human review. How support was checked

• ESPACE
  • … decider that halts on every input and visits at most \(2^{7n+4}\) work cells decides a language in ESPACE. to A succinctly represented state system may require an explicit exponential-size state description during deterministic reachability analysis while still remaining inside the class. demonstrates that continuity.
• Padding argument
  • … nondeterministic exponential-time language places its padded form in NP and transfers the assumed deterministic polynomial algorithm back to EXP. to A proof writes the padding function and both inclusion simulations explicitly, checking uniformity and rejecting malformed encodings before comparing asymptotic bounds..
• Space Hierarchy Theorem
  • Modern texts present it alongside diagonalization, universal simulation, configuration graphs, and constructible bounds.

Mechanisms

• Randomized Repetition and Error Amplification
  • This is amplification in the sense of the Chernoff bound and BPP.

    This sourceShows that bounded-error randomized computation can reduce error probability through independent repetition and a Chernoff-bound analysis.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 2 of 8 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://theory.cs.princeton.edu/complexity/ ×1

Registry ID ref:5de60913afe3 · see in the full table