**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_{0},
a_{1}, ... 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.

## No comments:

## Post a Comment