Computational Complexity

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

Type

Book chapter

Intellectual base

Textbook

Year

1994

ISBN

9780201530827

Link

https://openlibrary.org/books/OL1398106Mmatched

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

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.

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