Computational Complexity

Thursday, September 05, 2002

 

Posted by Lance

I heard of a nice new result from Russell Impagliazzo and Valentine Kabanets yesterday. Consider the language PI (Polynomial Identities) consisting of multivariate polynomials which are identically zero. PI is in co-RP by replacing the variables by random values and seeing if the result is zero. There is a lemma by Schwartz that implies this randomized algorithm will work with high confidence.

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

1. PI requires deterministic exponential time to solve.
2. The permanent does not have polynomial-size arithmetic circuits.
3. NEXP does not have polynomial-size Boolean circuits.

Here is a sketch of the proof. For a matrix A let A_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
(*) Perm(A) = Σ_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.

5:12 AM # 0 comments

Comment Feeds: This Post All