NP Is as Easy as Detecting Unique Solutions

Valiant, L. G., & Vazirani, V. V. (1986). NP Is as Easy as Detecting Unique Solutions. Theoretical Computer Science, 3975(86), 85-93.

Type

Journal article

Intellectual base

Primary research

Year

1986

DOI

10.1016/0304-3975(86)90135-0

Link

https://doi.org/10.1016/0304-3975(86)90135-0

Cited by

1 citation across 1 artifact.

Domain-specific

• Isolation lemma
  • … Assigning weights from a range of size twice the ground-set size yields a unique minimum feasible set with probability at least one half. to The Mulmuley–Vazirani–Vazirani matching method uses isolation to make a perfect matching unique before extracting it through algebraic calculations. demonstrates that continuity.

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:986688d93885 · see in the full table