ECCC-Report TR11-167https://eccc.weizmann.ac.il/report/2011/167Comments and Revisions published for TR11-167en-usWed, 12 Dec 2012 09:30:36 +0200
Revision 1
| Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances'' |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2011/167#revision1Assume that NP is not included in BPP. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm D for SAT there is a polynomial time samplable distribution such that D errs with probability at least 1/6-epsilon
on a random formula chosen with respect to that distribution. In this paper, we show how to increase the error probability to 1/3-epsilon.Wed, 12 Dec 2012 09:30:36 +0200https://eccc.weizmann.ac.il/report/2011/167#revision1
Paper TR11-167
| Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances'' |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2011/167Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to that distribution. In this paper, we show how to increase the error probability to $1/3-\epsilon$. We also generalize this result to the search version of SAT: we prove that for every randomized polynomial time algorithm $S$ searching for a satisfying assignment of a given formula, there is a polynomial time samplable distribution such that $S$ errs with probability at least $1-\epsilon$ on a random formula chosen with respect to that distribution.Fri, 09 Dec 2011 15:05:55 +0200https://eccc.weizmann.ac.il/report/2011/167