Impagliazzo and Wigderson showed that if E = DTIME ( 2 O ( n ) ) requires size 2 ( n ) circuits, then every time T constant-error randomized algorithm can be simulated deterministically in time \poly ( T ) . However, such polynomial slowdown is a deal breaker when T = 2 n , for a constant 0"> 0 , as is the case for some randomized algorithms for NP-complete problems.

Paturi and Pudlak \cite{PP} observed that many such algorithms are obtained from randomized time T algorithms, for T 2 o ( n ) , with large one-sided error 1 − \eps , for \eps = 2 − n , that are repeated 1 \eps times to yield a constant-error randomized algorithm running in time T \eps = 2 ( + o (1)) n .

We show that if E requires size 2 ( n ) nondeterministic circuits, then there is a \poly ( n ) -time \eps -HSG (Hitting-Set Generator) H : \bits O ( log n )+ log (1 \eps ) \ar \bits n , %(so that every linear-size Boolean circuit C with Pr x \bits n [ C ( x ) = 1 ] \eps will accept input H ( s ) for at least one seed s \bits r ). implying that time T randomized algorithms with one-sided error 1 − \eps can be simulated in deterministic time \poly ( T ) \eps . In particular, under this hardness assumption, the fastest known constant-error randomized algorithm for k -SAT (for k 4 ) by Paturi et al.~\cite{PPSZ} can be made deterministic with essentially the same time bound. This is the first hardness versus randomness tradeoff for algorithms for NP-complete problems. We address the necessity of our assumption by showing that HSGs with very low error imply hardness for nondeterministic circuits with ``few'' nondeterministic bits.

Applebaum et al. showed that ``black-box techniques'' cannot achieve \poly ( n ) -time computable \eps -PRGs (Pseudo-Random Generators) for \eps = n − (1) , even if we assume hardness against circuits with oracle access to an arbitrary language in the polynomial time hierarchy. We introduce weaker variants of PRGs with \emph{relative error}, that do follow under the latter hardness assumption. Specifically, we say that a function G : \bits r \ar \bits n is an ( \eps ) -re-PRG for a circuit C if (1 − \eps ) Pr [ C ( U n ) = 1 ] − Pr [ C ( G ( U r ) = 1 ] ( 1 + \eps ) Pr [ C ( U n ) = 1 ] + We construct \poly ( n ) -time computable ( \eps ) -re-PRGs with arbitrary polynomial stretch, \eps = n − O (1) and = 2 − n (1) . We also construct PRGs with relative error that fool \emph{non-boolean distinguishers} (in the sense introduced by Dubrov and Ishai).

Our techniques use ideas from \cite{PP,TV,AASY15}. Common themes in our proofs are ``composing'' a PRG/HSG with a combinatorial object such as dispersers and extractors, and the use of nondeterministic reductions in the spirit of Feige and Lund \cite{FeigeLund}.