Second proof that P != NP

After carefully examining my first proof that P != NP and the responses to it, I became convinced that it was not complete…one serious reviewer found a problem, and I haven’t found a way to fix it yet.

I have decided to post a second proof that P != NP, which is harder to follow and has slightly more challenging-to-understand details.  Please find it below.

– – –
Outline:

1 > Define the alternate model of Turing machines
2 > Confirm that the BGS-B oracle is still such that P^B != NP^B, and note that “(given B) P^B != NP^B” does not relativize
3 > Now, we want to prove, given some TM-as-oracle X: P^X = NP^X –> P^(X,X’) = NP^(X,X’) –> P^X’ = NP^X’
4 > Now prove: (P = NP) –> (P = NP relativizes)
5 > This proves P != NP, because P = NP implies P = NP relative even to the oracle B.

1 > Definition of Turing machine.

An edge is:

N x N x ([0,4095] in N) x ([0,4095] in N) x ([0,4095] in N)
A Turing machine is:

A set of edges and a set of TMs that serve as oracles, OR the integer 0 (a blank Turing machine with no edges that rejects everything.)

I.e.: edge x edge x edge x edge x edge x … x edge x TM x TM x TM x … x TM

(A four-tape machine, with an oracle tape; a main tape; a “starting configuration tape” that takes as input the start state, accept state, reject state, and initial tape head position; and a “starting configuration tape” for the oracle machine.)

Every TM must be finite.

A relativized TM is one where the TM at the end changes from 0 to any other TM.

Even-numbered states (2, 4, 6, …) are oracle states, associated with the set of TMs-as-oracles, while the odd-numbered states (1, 3, 5, …) are the regular transition states.

In this version, every oracle acceptance or rejection causes the oracle to return more than just “1” if it accepts and “0” if it rejects. Instead, each oracle will return “1”, followed by the position of the tape head (with the appropriate formatting), followed by the FULL COMPUTATION HISTORY OF THE ORACLE ON ITS INPUT (not including the configuration tape or other tapes besides the main one). If the machine rejects, it will do the same thing, except with an initial “0” instead of an initial “1.” Note, traversing the machine without reading or writing to the tape costs only one cycle (not the usual linear time).

2 > Baker-Gill-Solovay.

Note that our new model of computation (for Turing machines) is still Turing complete, and that it represents a way to formalize relativization.

See: zoo.cs.yale.edu/classes/cs468/BGS.pdf for a treatment of the second half of the Baker-Gill-Solovay result; it should be clear that it regardless of the Turing machine model used.

Thus, we have that, given the precise definition of B in the resource, “P^B != NP^B.”

Note that this result does not relativize (consider an EXPTIME-complete oracle, which absorbs the EXPTIME oracle B and causes P = NP to be true). On the other hand, the answer to the existential question–does there EXIST an oracle Y relative to which P^Y != NP^Y?–is yes and this relativizes. It is the notion that a specific, precisely defined oracle separates P != NP that does not relativize, and this distinction is important because this is why the full proof that P != NP does not relativize.

3 > For all valid TMs X , X’ s.t. X is X’ minus one edge: P^X = NP^X –> P^(X,X’) = NP^(X,X’) –> P^X’ = NP^X’

This proof has two parts. We start with:

P^X = NP^X –> P^(X,X’) = NP^(X,X’)

Note that the notation “^(X,X’)” means that we have two oracles–X and X’.

At this point, we need to show that P^(X,X’) is a subset of P^X.

To do this, we’ll show that there exists a P^X algorithm A1 that decides the same language as any fixed P^(X,X’) algorithm A2.

Basically, we simulate the X’ oracle in polynomial time. To do this, we make queries to X, and whenever X rejects, we examine the computation history that gets dumped to the oracle tape of the main machine. Then, we determine if the rejection occurred where the edge was to be added; if it was, we brute-force simulate the transition of this edge, take into account where the edge should have left the configuration of the machine, and “reboot” by querying X again with a different starting configuration. We repeat this process until we have determined for certain if X’ would accept or reject the input in question.

Because the class P is closed under composition, we see that the polynomial blowup in computation cycles taken is not of any consequence, and thus we can still simulate any language we were previously able to simulate in P^(X,X’) with only a P^X machine.

Now, we must show that P^X’ is a subset of P^(X,X’). This means that for any P^X’ algorithm, there is a P^(X,X’) algorithm that decides the same language. This proof is trivial; given a P^X’ algorithm, we merely construct an equivalent algorithm that decides the same language that is P^(X,X’) but avoids its X oracle state.

Finally, we must observe that similar logic yields proofs that NP^(X,X’) is a subset of NP^X, and that NP^X’ is a subset of NP^(X,X’).  This holds because each NP machine may easily “call” deterministic polynomial subroutines in the course of its execution, the same way that P machines can.  Somewhat surprisingly, we can see that once a TM-as-oracle has been constructed relative to which P and NP are equal, every oracle constructed from larger machines (i.e., machines that contain all the same edges and then additional edges) will also yield relativized versions of P and NP that are equal.

4 > (P = NP) –> (P = NP relativizes)

Based on Step #3, we have that (omitting the obvious quantifiers) P^X = NP^X –> P^X’ = NP^X’. This means that, by induction, if we are given that P = NP relative to a trivial oracle, we can say that any constructible Turing machine with a finite number of edges can be proved to be such that, relative to an oracle for this Turing machine, P = NP. Thus we have that (given the assumption that P = NP) P = NP relativizes.

5 > P != NP

Given that P = NP –> P = NP relativizes (step 4), and that P = NP does not relativize (which follows from step 2), we see that by contraposition, P != NP.

Proof That P != NP.

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.