Talk:Valiant–Vazirani theorem

I have read this exposition, and I am still confused. If we are given a SAT problem, then we don't know the number of solutions. So we don't know what k should be. So we can make a bunch of formulas, one for each k, and there is a reasonable chance that one of them has a unique solution, so giving this formula to SAT-UNIQUE would solve our original problem. But this does not yield the desired reduction, because we do not know which formula to pass to SAT-UNIQUE (or if we pass them all, as there are only n of them, we do not know which answer to use). 130.60.5.218 10:55, 15 January 2007 (UTC)[reply]

The argument was stated in a confusing way. But the point is that the reduction has one-sided error: if the original formula is unsatisfiable, then all the output formulas are certainly unsatisfiable. Thus, once at least one of the formulas gives answer YES, the original formula must be satisfiable (and conversely, if the original formula is satisfiable, then this happens with a decent probability).—Emil J. 10:22, 3 December 2023 (UTC)[reply]

References[edit]

Maybe we should add this article as a reference: http://andysresearch.blogspot.com/2007/06/paths-to-discovery-valiant-vazirani.html I think it is the best exposition of this theorem. — Preceding unsigned comment added by 157.92.4.71 (talk) 22:35, 5 October 2011 (UTC)[reply]