Talk:Valiant-Vazirani theorem
From Wikipedia, the free encyclopedia
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)
