The Complexity of Enumeration and Reliability Problems

Valiant, L. G. (1979). The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing, 8(3), 410-421.

Type

Journal article

Intellectual base

Primary research

Year

1979

DOI

10.1137/0208032

Link

https://doi.org/10.1137/0208032

Cited by

1 citation across 1 artifact.

Domain-specific

• Sharp Satisfiability (#SAT)
  • Parsimonious reductions preserve counts exactly; Turing and metric reductions support other completeness results but license different inferences.

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:620f75f16726 · see in the full table