We say a language L is in i.o.-C for a complexity class C if there is an A in C such that for infinitely many n, A and L agree on strings of length n (for all x of length n, x is in A if and only if x is in L). Straightforward diagonalization shows that EXP is not in i.o.-P.

However we showed a relativized world where NEXP is in i.o.-NP in a recent paper (Theorem 18).

The construction is not particularly difficult but rather surprising: There is a possibility that one can get exponential improvement for nondeterministic computation for infinitely many input lengths.

Also consider the following facts: NEXP is not in i.o.-co-NP by straight diagonalization. If NEXP is is in i.o.-NP then

- NEXP is in i.o.-EXP
- EXP is in i.o.-NP and thus EXP is in i.o.-co-NP (since EXP is closed under complement).

NEXP in i.o.-NP is not one of my most complicated relativization results, but definitely one of the strangest.

## No comments:

## Post a Comment