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.

_{ij}represent A with the ith row and jth column removed. Consider the self-reduction from the permanent of a (k+1)×(k+1) matrix to permanents of k×k matrices

_{j}a

_{1j}Perm(A

_{1j})

Suppose that the permanent has polynomial-size arithmetic circuits.
Then P^{#P} is computable in NP^{PI} 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} ⊆ NP^{PI}. If PI is computable
in subexponential time then NEXP is in nondeterministic subexponential
time, contradicting the nondeterministic time hierarchy.

## No comments:

## Post a Comment