In a world of
It has been known for a long time that existence of suitable pseudorandom generators implies that , i.e. every problem solvable by a probabilistic polynomial alogorthm can be derandomized. I claim that the converse is true. If it happens that , then pseudorandom generators exist.
1. Pseudorandom generators
A pseudorandom generator is a deterministic algorithm which produces long strings which look random from short strings which are truly random. This covers a variety of devices, from general purpose PRGs fooling any efficient observer to special purpose, say pairwise independence generators. The parameters of a PRG are
- Amount of stretching.
- Level of “looking random”.
- Computational cost of the algorithm.
For derandomizing, it is sufficient to use PRGs that run in time exponential in seed length, whose output looks random to linear-time observers. Indeed, one hopes the stretch to be exponential. Thus requirements on PRGs are much relaxed compared to usual requirements.
Theorem 1 If PRGs that run in time exponential in seed length, have exponential stretch and whose output looks random to linear-time observers exist, then .
Proof: First assume the algorithm to be derandomize has linear running time. Combine it with PRG to get a randomized algorithm which is functionally equivalent, has polynomial running time, and uses random bits. Then derandomize by brutally running on all possible values of bits previously thought of as random.
“Random looking” is specified as follows. For every polynomial , no probabilistic -time algorithm can distinguish the PRG’s output from a truly random string with gap .
With this uniform formulation, we can put effectively in . I.e. for every problem in and every polynomial , we obtain a deterministic polytime algorithm such that no -time algorithm can find an input on which the algorithm errs. We call this -effectively solving the problem.
2. Reversing the connection
Assume . The goal is to construct PRGs.
A random function of exponential stretch has the desired pseudorandomness feature. Idea: Just derandomize this choice! But this is a search problem, and deals with decision problems and not search problems. So we must first reduce -search problems to -decision problems.
2.1. From -search problems to -decision problems
Here is our current search problem: Wanted PRG is, for each , a set of length strings, such that uniform distribution on fools -time observers. Note that validity of solutions can be checked in probabilistic polynomial time.
More generally, -search problems require finding PPT
Claim: Every -search problem reduces to a -decision problem.
Remiscent of reduction of -search problems to -decision problems, which goes as follows: consider the following sequence of decision problems: given a prefix , is one of and the prefix of a solution ?
Here, need merely an estimate on the probability that a prefix does extend into a prefix of a solution.
2.2. Targeted derandomizers
Above construction merely shows that problems can be effectively solved by deterministic algorithms with small error. This is not quite .
Theorem 2 iff there exists a targeted derandomizer of exponential stretch.
A targeted derandomizer is a family of PRGs. Think of auxiliary parameter as describing the environment. The observer knows it as well as the generator, and nevertheless, must be fooled uniformly whatever the state of the environment.