Friday, September 26, 2008

An Accidental Theorem

First a reminder that the FOCS early registration/hotel registration deadline is a week from today, October 3.

At the Dagstuhl open problem session last week I gave the following conjecture that I had worked on with Harry Buhrman and Rahul Santhanam the week before in Amsterdam.

(*) NEXP is not contained in NP/nc for any constant c.
NEXP is the class of languages computable in nondeterministic time 2poly(n), NP is nondeterministic polynomial time and nc represents advice, non-uniform information of up to nc bits that depend only on the input length. No one would think (*) is false, the question was to prove it without using any assumptions.

I described the failed approach using derandomization via IKW. I also mentioned the best known separation, that NEXP is provably not in NP/no(1).

Later someone asked me how to prove that known result. I tried to reconstruct the proof on the fly. I ended up with a proof that also showed (*) and didn't use any derandomization.

What's the lesson? Sometimes a proof shows up in the strangest places, like when accidentally proving something stronger when you meant to prove something weaker.

Proof of (*): Assume (*) false. NE (the class of problems computable in nondeterministic time 2O(n)) would be in NTIME(nk)/nc for some k since NE has linear-time complete sets. We now have EXP is in NEXP is in NP/nc is in NE/nc is in NTIME(nck)/nc2 (by translation) in DTIME(2nck)/nc2. From this you can use standard diagonalization to get a contradiction.

Later Harry, Rahul and I strengthened the result to show

NEXP is not contained in PNP[nc]/nc for any constant c. (That's polynomial time with nc queries to some NP-complete set and nc bits of advice.)
The proofs relativize and you can't do better with the size of the advice or number of queries with a relativizable proof.

1 comment:

  1. Do have a write up available on the proof of your theorems?