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.
Facts
Classification
Statement Form Statement Form StatementIf there is a polynomial time algorithm for unambiguous-SAT, then NP equals RP. 1 Connections
Has Statement Form
In Branch
Source Valiant-Vazirani theorem, Wikipedia
In the Other Atlases
Credited To
Also in Computing Atlas: credited with this subject.
Also in Computing Atlas: credited with this subject.
Sources
1. Valiant-Vazirani theorem, Wikipedia
Lead section
The Valiant-Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous-SAT, then NP = RP.
Lead paragraph, attribution sentence
It was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986.
- In Branch: Computational Complexity Theory, Lead sentence
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.