Valiant-Vazirani Theorem
Consider the following promise problem: Given a boolean formula that has at most one satisfying assignment, decide whether it is unsatisfiable or it has exactly one satisfying assignment. The Valiant-Vazirani theorem says that, if this problem is solvable in polynomial …