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

Link

https://doi.org/10.1017/CBO9780511804090

Cited from

computer_science

Cited by

5 citations across 5 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.

Domain-specific

• Approximation Algorithm
  • Thus the field manages both constructive choices and limits on what efficient computation can guarantee.
• 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.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. 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