Valiant-Vazirani Theorem

The Valiant-Vazirani Theorem, proved by Leslie Valiant and Vijay Vazirani in their 1986 paper NP is as Easy as Detecting Unique Solutions, shows that if there is a polynomial-time algorithm for deciding satisfiability instances already known to have at most one solution, then NP equals RP. The theorem demonstrates that the Boolean satisfiability problem remains as hard in this uniquely-solvable special case as it is in general, by way of a randomized reduction that isolates a single solution with reasonable probability.