Computational Complexity

Friday, September 26, 2008

 
An Accidental Theorem

Posted by Lance

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/n^c for any constant c.

NEXP is the class of languages computable in nondeterministic time 2^poly(n), NP is nondeterministic polynomial time and n^c represents advice, non-uniform information of up to n^c 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/n^o(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 2^O(n)) would be in NTIME(n^k)/n^c for some k since NE has linear-time complete sets. We now have EXP is in NEXP is in NP/n^c is in NE/n^c is in NTIME(n^ck)/n^c2 (by translation) in DTIME(2^nck)/n^c2. 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 P^NP[nc]/n^c for any constant c. (That's polynomial time with n^c queries to some NP-complete set and n^c 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.

6:05 AM # 1 comments

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

   5:21 AM, September 28, 2008

Comment Feeds: This Post All