![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)