Computational Complexity


Creative Commons License
This work is licensed under a Creative Commons License.

Powered by Blogger™

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 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.

4:13 AM # 0 comments

Comment Feeds: This Post All

Links to this post:

Create a Link

Weblog Home