[My Computational Complexity Web Log] A Little Theorem
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 2poly(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 a0, a1, ... with |an| 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 an 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 an 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 EXPttNP is in NEXP/poly where EXPttNP are the set of languages nonadaptively reducible to an NP set in exponential time.
Posted by Lance Fortnow to My Computational Complexity Web Log at 1/30/2004 04:13:10 AM