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.
Do have a write up available on the proof of your theorems?
ReplyDelete