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.

* * * * *

Clarifications –

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.

Consider glancing at the reddit thread here:

http://www.reddit.com/r/compsci/comments/1oo9q7/an_unevaluated_proof_that_p_np/

Leave a comment if you have anything to say! I really want to get this proof checked.

I have checked it for you, looks correct.

Note, I caught a small typo. The sentence that reads: “C is simulated for |C|^|I|+|I| steps, where I is the input to the machine.” should read “C is simulated for |I|^|C|+|C| steps, where I is the input to the machine.” I saw one other, too, but would prefer to leave the original articulation intact for now. (There is a sentence where the word “do” is used instead of “does.”) Finally, I can’t seem to fix the timezone on the blog.

I don’t understand how you’re assigning an index to every NP machine. Are you claiming that any arbitrary NP machine M is necessarily comprised of parts T, G, and C as described?

Edit: I misread your post at first, I don’t mean to say thateverymachine is formed this way, only that every NP language can be decided by a machine that can be formed in this way.“Yes, that is my claim. This indexes (or members of the enumeration) don’t run in polynomial time, but this enumeration captures what NP is by allowing every NP language to be captured by the indexing.

The idea is that the machine brute force guesses every possible certificate, and then passes each certificate to the polynomial time checker. If the checker ever accepts, then the machine accepts. This is how NP usually works–except that it is assumed to guess the right certificate “nondeterministically” or automatically, not via brute force.”

I see. So you are not enumerating all NP machines. You are only enumerating (at least) one machine for each NP language. But there could be plenty of other machines that decide NP languages yet do not work in this particular way with T, G, and C. This looks like it might be a flaw in the proof because you’re making assumptions about how an NP algorithm should work rather than considering the problem in full generality. I haven’t read the rest of the proof yet though and maybe it still works. Do you believe that what I have pointed out is not a flaw? If so could you briefly explain why?

I guess I should clarify what I mean by “NP algorithm.” I don’t mean a nondeterministic polytime Turing Machine. I mean any deterministic algorithm that decides a language in NP. You are trying to enumerate the deterministic machines for NP languages, right?

I guess I see now. I was getting confused by this sentence: “Given a main machine M, we want to describe three machines that comprise it.” If I understand correctly you mean something more like “Given a language in NP, we want to describe a particular three-part machine that decides it.”

awein1990: Yes, I don’t think it’s a flaw, and yes your rephrasing is basically correct. It’s a “three-part machine” that includes a supervising algorithm that simulates the other two algorithms. Further, you’re right that there are other machines that do not work in this way that decide NP languages. My goal is to capture every NP language at least once, and that is what happens with this scheme.

One more conventional system for enumerating NP machines is to list all nondeterministic machines with a polynomial time clocking (that forces the algorithm to halt and reject if its branches haven’t finished computing in time). This system also works, even though there are other machines that decide NP languages other than these.

I follow everything except step 3. Here’s where I’m confused on step 3: The EXP machine X takes as input a machine (T,G,C) where C does not use any oracle. The language diagNP^O is defined the same as diagNP except the checker C is allowed to use the oracle O. It looks like you’re trying to decide diagNP^O by simulating X on input M = (T,G,C) where C can use the oracle O. But this doesn’t work because X is only guaranteed to work on machines where C doesn’t use an oracle. Am I missing something?

One small clarification first: X doesn’t replace the whole triple, it replaces only G. So you go from (T,G,C) to (T,X,C). I probably could have made that more clear in the write-up.

To visualize this, imagine a diagram like the following:

M1 M2 M3 M4 M5 …

M1

M2

M3

M4

M5

…

(I had to omit the 1’s and 0’s due to WordPress being dumb…sorry). The diagonal of the diagram above represents what you get when you have M1 = (T,G,C)_1, M2 = (T,G,C)_2, … etc. running on themselves. The rows represent the NP machines that I am simulating, while the columns represent the NP machines I’m simulating on (but only at the places where I’ve filled in 1’s or 0’s). The filled in diagonal is the language diagNP.

When I replace G with X, I do it only in the rows. This will yield the exact same diagonal.

Now, when I relativize by adding an oracle O to every machine T, G, X, and C that appears in any computation or index, I’ll get the same structure. The key is that although I’ve technically added an oracle to X, it hasn’t changed a bit because it has no oracle access (just as G had no oracle access). So it can function the same way as before, and I just have a checker that runs in P^O and the same EXPTIME machine X to multitask over in EXP^O.

T^O,X,C^O is guaranteed to work when simulated because T,G,C works on the diagonal (which is all we care about) in the non-relativized world, T,X,C works on the diagonal in the non-relativized world, and so since adding an oracle to T,G,C works on the diagonal, so does adding an oracle to T,X,C.

Is that any clearer? I definitely understood your point, although I’m not sure if I’ve responded to it clearly yet.

So to clarify: even in the non-relativized case, each of your machines T,G,C,X is technically an oracle machine, i.e. the machine description can include oracle calls. The machine description does not specify what the oracle actually is though. In the non-relativized case, the oracle is taken to be something trivial, say the empty language. This way you can “plug in” any oracle O to each machine in the list and still have a complete enumeration that captures all languages is NP^O. Is this what you were going for?

I’m still questioning whether X works properly in the relativized case. It seems like you’re defining X as follows. We are assuming diagNP is in EXP and so there is an EXPTIME algorithm that decides diagNP. X takes as input a tuple M=(T,G,C) of oracle machines (as explained above). X runs the EXPTIME procedure for diagNP and outputs a single guess: a correct witness that will cause C (with trivial oracle “plugged in”) to accept input M. (If no such witness exists because M is in diagNP then X can output a single garbage guess.)

My first question: Is it obvious that such an X even exists? Sure, X can decide whether or not M accepts itself in EXPTIME but can it actually find a witness? I don’t see any self-reducibility.

But the problem that worries me most is this one: the idea for relativizing this is to “plug in” the oracle O to all machines and use the same argument. But now in order for X to work correctly it needs to find a witness that will cause C with oracle O “plugged in” to accept input M. But all we know is that X can find a witness that will cause C with trivial oracle “plugged in” to accept input M. I see no reason why these witnesses should be the same.

Let me know what you think.

Yikes…after thinking about this comment and your previous one a little more, I think you are right. My attempt is not quite right, or at least incomplete. Thanks for finding the mistake.

Basically, I was assuming that replacing G with X would allow adding an oracle to make everything work. But as (I think) you are suggesting, there’s no guarantee that X will continue to work in the presence of an oracle. That was just my hasty assumption.

Again, thanks for helping me work this out. Back to the drawing board!