Since we now know Primality is in P, PI is the best remaining example of a problem with an efficient probabilistic algorithm but no known deterministic algorithm. Unlike primality, giving even a weak derandomization for PI will be difficult as it will lead to circuit lower bounds.
Theorem: (Impagliazzo-Kabanets) At least one of the following must be true
- PI requires deterministic exponential time to solve.
- The permanent does not have polynomial-size arithmetic circuits.
- NEXP does not have polynomial-size Boolean circuits.
Suppose that the permanent has polynomial-size arithmetic circuits. Then P#P is computable in NPPI by the following algorithm: Guess the arithmetic circuits for the Permanent for all sizes k×k up to n×n for some appropriate n. Use PI to verify (*) for each k<n. If the test is correct on all lengths than the circuits are correct. Use the circuits to compute the Permanent which is #P-complete.
Now suppose NEXP has polynomial-size circuits. By Impagliazzo-Kabanets-Wigderson this implies NEXP = MA ⊆ PH ⊆ P#P ⊆ NPPI. If PI is computable in subexponential time then NEXP is in nondeterministic subexponential time, contradicting the nondeterministic time hierarchy.