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.