Valiant-Vazirani theorem
Encyclopedia
The Valiant–Vazirani theorem is a theorem in computational complexity theory
. It was proven by Leslie Valiant
and Vijay Vazirani
in their paper titled "NP is as easy as detecting unique solutions" published in 1986. The theorem states that if there is a polynomial time algorithm
for Unambiguous-SAT, then NP
=RP
.
The theorem implies that even if the number of satisfying assignments is very small, SAT
(which is an NP-complete
problem) still remains a hard problem.
to decide whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment. In the first case a Unambiguous-SAT algorithm should reject, and in the second it should accept the formula. If the formula has more than one satisfying assignment then the behavior of the Unambiguous-SAT algorithm does not matter. Unambiguous-SAT belongs to complexity class UP
.
The proof of Valiant–Vazirani theorem creates a probabilistic reduction from SAT to a limited number of instances of Unambiguous-SAT. By this reduction, if the original formula was unsatisfiable, none of Unambiguous-SAT problems are satisfiable. And if the original formula is satisfiable, then with probability ≥ 1/8, at least one of the Unambiguous-SAT instances has a unique satisfying assignment. Note that this probabilistic reduction introduces some error; however, the proof shows that the error is single-sided and completely avoids false-positive
s. The reduction relies also on universal hash functions to map the original SAT formula to multiple Unambiguous-SAT instances. By choosing different sizes of the hash set the authors create one instance of Unambiguous-SAT to have a solution with probability ≥1/8, if the original problem was satisfiable.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. It was proven by Leslie Valiant
Leslie Valiant
Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
and Vijay Vazirani
Vijay Vazirani
Vijay Virkumar Vazirani is an Indian American Professor of Computer Science at Georgia Tech.He received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian...
in their paper titled "NP is as easy as detecting unique solutions" published in 1986. The theorem states that if there is a polynomial time algorithm
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
for Unambiguous-SAT, then NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
=RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
.
The theorem implies that even if the number of satisfying assignments is very small, SAT
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
(which is an NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem) still remains a hard problem.
Proof outline
Unambiguous-SAT is the promise problemPromise problem
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs. Unlike decision problems, the yes instances and no instances do not exhaust the set of all inputs...
to decide whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment. In the first case a Unambiguous-SAT algorithm should reject, and in the second it should accept the formula. If the formula has more than one satisfying assignment then the behavior of the Unambiguous-SAT algorithm does not matter. Unambiguous-SAT belongs to complexity class UP
UP (complexity)
In complexity theory, UP is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input...
.
The proof of Valiant–Vazirani theorem creates a probabilistic reduction from SAT to a limited number of instances of Unambiguous-SAT. By this reduction, if the original formula was unsatisfiable, none of Unambiguous-SAT problems are satisfiable. And if the original formula is satisfiable, then with probability ≥ 1/8, at least one of the Unambiguous-SAT instances has a unique satisfying assignment. Note that this probabilistic reduction introduces some error; however, the proof shows that the error is single-sided and completely avoids false-positive
Type I and type II errors
In statistical test theory the notion of statistical error is an integral part of hypothesis testing. The test requires an unambiguous statement of a null hypothesis, which usually corresponds to a default "state of nature", for example "this person is healthy", "this accused is not guilty" or...
s. The reduction relies also on universal hash functions to map the original SAT formula to multiple Unambiguous-SAT instances. By choosing different sizes of the hash set the authors create one instance of Unambiguous-SAT to have a solution with probability ≥1/8, if the original problem was satisfiable.