Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers (Preliminary version)
Andrew Drucker · 2013
We give two nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In these theorems one assumes that a target function f is mildly hard against nondeterministic circuits, and concludes that the direct product f t is extremely hard against (only polynomially smaller) probabilistic circuits. The main advantage of these results compared with previous DPTs is the strength of the size bound in our conclusion. As an application, we show that if NP is not in coNP=poly then, for every PPT algorithm attempting to produce satisfying assigments to Boolean formulas, there are innitely many instances where the algorithm’s success probability is nearly-exponentially small. This furthers a project of Paturi and Pudl ak [STOC’10].