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''

摘要

Assume 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-epsilonon a random formula chosen with respect to that distribution. In this paper, we show how to increase the error probability to 1/3-epsilon.