Computational Complexity

Goldreich, O. (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press.

Type

Book

Intellectual base

Review or monograph

Year

2008

Link

no authoritative link yet

Cited by

4 citations across 4 artifacts.

Domain-specific

• Computational problem
  • The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.
• Constructible function
  • Time- and space-constructibility are distinct, unary or binary input conventions affect costs and the function must also satisfy growth and monotonicity qualifications in many theorems.
• Parsimonious reduction
  • The solution correspondence must be bijective or count-preserving for every instance, a stronger condition than preserving only existence; encoding and polynomial computability matter.
• Unary language
  • The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

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:53051fb7699b · see in the full table