Computational Complexity

Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.

Type

Book

Intellectual base

Textbook

Year

1994

ISBN

9780201530827

Link

https://openlibrary.org/isbn/9780201530827verified

Cited by

6 citations across 6 artifacts.

Domain-specific

• ESPACE
  • The entry treats decision languages under standard deterministic-space conventions; it makes no practical memory forecast and does not infer tractability from class membership.
• EXPSPACE
  • EXPSPACE is the deterministic space-complexity class \(\bigcup_{k\ge 1}\operatorname{DSPACE}(2^{n^k})\), consisting of decision problems solvable using exponential space in the input length.
• Linear speedup theorem
  • For suitable time bounds and multitape models, a machine running in f(n) time can be simulated by another using the same tape count and a larger alphabet in at most c f(n) plus linear overhead for any fixed c>0.
• PolyL
  • PolyL contains languages decidable deterministically using at most a polynomial in the logarithm of input size as workspace.
• Reduction (complexity)
  • The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.
• Sharp Satisfiability (#SAT)
  • Listed in the references but not attached to a specific claim.

Verification

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

Does it back the claim? Not recorded. Neither this nor any other of the 6 citations of this work carries a recorded support check.

Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.

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.

Registry ID ref:7e785f9d6b6c · see in the full table