Proof Overview –
1 > diagNP is not in NP relativizes.
2 > diagNP is in coNEXP.
3 > diagNP is in EXP –> “diagNP is in EXP” relativizes.
4 > diagNP is in EXP –> “NP != EXP” relativizes.
5 > relative to HELLER: NP^HELLER = EXP^HELLER.
6 > NP != EXP does not relativize.
7 > diagNP is not in EXP.
8 > EXP != coNEXP.
9 > P != NP.
* * * * *
HELLER is an oracle from a 1984 paper by Hans Heller that he proves is such that relative to this oracle HELLER, NP = EXP. Note that Heller refers to EXP as “EP” in his paper.
Step 5 is the step that doesn’t relativize, though I don’t prove this.
diagNP is defined as: the language of NP indexes (the indexing is described below) that reject themselves.
diagNP is in coNEXP because simulating nondeterministic machines for k cycles to check for acceptance is in NEXP, and simulating nondeterministic machines for k cycles to check for rejection is in coNEXP.
Proof of Step 3 –
We give the following indexing for NP:
Given a main machine M, we want to describe three machines that comprise it: a multitasker T, a guesser G, and a checker C.
We describe the guesser G first. G begins with a 0 on its tape, and then outputs all possible strings in order.
The checker C accepts its input in some cases, and never halts in others. C does not reject any inputs.
The multitasker T behaves in the following way: T simulates one step of the guesser so that the guesser produces one certificate. Then, G’s guess is passed to C. C is simulated for |C|^|I|+|I| steps, where I is the input to the machine. If C accepts the guess in that amount of time, then the whole machine M accepts and halts. Otherwise, T simulates another step of G, repeating the above process until G has guessed 2^(|I|^|C|+|C|) different guesses. If all of G’s guesses are rejected, then the machine rejects.
Consider the language diagNP, which is the language of all self-rejecting NP machines as described above. If we wished to simulate diagNP directly, we might have to simulate the guesser for 2^(|G+T+C|^|C|)+|C| cycles, which is super-exponential time.
However, if diagNP is in EXP, then when consider M(M), we know that we can replace the G in the first occurrence of M with a single EXPTIME guesser X that runs for 2^(|G+T+C|^k)+k for some fixed k, that doesn’t change even when the machine M = (G,T,C) changes.
It is critical to note that this new EXPTIME machine, like the old guesser G, do not need to use the oracle. There is only one fixed machine, and it doesn’t ever access the oracle because the oracle, in this non-relativized world, is trivial.
Now, let us consider whether or not “diagNP is in EXP” is true relative to an oracle O; that is, whether or not diagNP^O is in EXP^O.
With this indexing and with the assumption and substitution discussed above, it should be clear that it is. There are still three parts to an NP machine: the multitasker T, the guesser G (or its replacement, the more efficient guesser X), and checker C. We can see that X alone runs in time 2^(|I|^k+k), while C runs in time |I|^|I|+|I|. (Note that I is the input machine, which varies only slightly from the main machine.) To simulate the full computation, one must simulate for (2^(|I|^k+k))*(|I|^|I|+|I|) cycles, which is clearly still exponential time. Thus relative to our oracle, diagNP remains in EXP. QED.