Computational Complexity

Friday, January 30, 2004

 
A Little Theorem

Posted by Lance

Here's a simple result I have seen several times recently, a bit surprising when you first see it.

Theorem: co-NEXP is in NEXP/poly.

NEXP are the languages accepted in nondeterministic time 2^poly(n). A language L is in C/poly for a complexity class C if there is a language A in C and a list of strings a₀, a₁, ... with |a_n| bounded by a polynomial in n such that x is in L if and only if (x,a_|x|) is in A.

I don't know who first showed this theorem and since the proof is rather simple it may have never been published. Let K be a complete set for NEXP and the polynomial length advice a_n for strings of length n is just the number of strings of length n in K. To nondeterministically check that y of length n is not in K, just guess a_n strings other than y of length n and verify they are in K.

This kind of result does not likely hold for NP. Yap shows that if co-NP is in NP/poly then the polynomial-time hierarchy collapses to the third level. This theorem above does not imply co-NEXP has subexponential nondeterministic circuit since exponential circuits might be required to describe the exponential computation.

Harry Buhrman noticed you can strengthen the result to show that EXP_tt^NP is in NEXP/poly where EXP_tt^NP are the set of languages nonadaptively reducible to an NP set in exponential time.

4:13 AM # 0 comments

Comment Feeds: This Post All