• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

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

P. 203-2011.

Assume that $\NP\not\subset\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-\eps$ on a random formula chosen with respect to that distribution. A challenging problem is to increase the error probability to the maximal possible $1/2-\eps$ (the random guessing has success probability 1/2). In this paper, we make a small step towards this goal: we show how to increase the error probability to $1/3-\eps$.