“Almost Proof” that P != NP cannot be proved, revised again

As you may have noticed, I have a tendency to make mistakes in these proofs.  Please see the previous proof attempts on the blog for details on any statement I make below that you’re not sure of.  Leave a comment if you find an error in my reasoning–thanks.

ZFC is inconsistent –> PROOFS is in P

PROOFS is not in P –> ZFC is consistent

ZFC is consistent –> (PROOFS is not in P) is unprovable

ZFC is consistent –> PROOFS is NP-complete

ZFC is consistent –> (PROOFS is NP-complete) and ((PROOFS is not in P) is unprovable)

 

Posted in Uncategorized | Leave a comment

ZFC is consistent –> P != NP cannot be proved. (Revised.)

[Updated:  01-12-2014]

1 – If ZFC is consistent, ZFC proofs are NP-complete.

2 – If ZFC proofs are NP-complete, then:  ZFC is inconsistent –> P = NP.

3 – If ZFC proofs are NP-complete, then:  P != NP –> ZFC is consistent.

4 – If ZFC is consistent, then P != NP cannot be proved in ZFC.

1) If ZFC is consistent, then there exist both theorems and non-theorems of ZFC. Based on any given SAT instance, we can construct a proposition that is an existentially quantified boolean proposition, where each variable is itself intended to be a proposition. For example: “there exists x1 s.t. there exists x2 s.t. there exists x3 s.t. (x1 ^ x2 ^ !x3) v (x3 ^ !x2) v (!x1 ^ !x1 ^ x3 ^ !x2 ^ x1)”. For each variable x1, x2, … , x_n, let x_i be one of two propositions from ZFC: provable_prop or !provable_prop (i.e., the negation of provable_prop).

If the initial SAT instance that we are mapping to a ZFC proposition is satisfiable, then we need only select x1, x2, … , x_n so that each x_i is either provable_prop or !provable_prop and the proposition is satisfied. Once we’ve done this, we’ll find that the resulting proposition simplifies to provable_prop, which is itself a theorem, implying that there do indeed exist propositions x1, x2, … , x_n s.t. the main proposition is a theorem.

On the other hand, if the initial SAT instance is unsatisfiable, then the main ZFC proposition that we map to will have no possible assignments to the literals (x1, x2, … , x_n) that will yield a provable proposition. This is clear because the ZFC proposition simplifies to a contradiction, which cannot be proved if ZFC is consistent.

So, considering the decision problem PROOF, which is to decide if, given a ZFC proposition and a string of all 1′s, there exists a proof of the proposition of length <= the length of the string of 1′s, we can now show that:

We wish to show: If ZFC is consistent, PROOF is NP-complete.

We showed a reduction from SAT to PROOF above that is contingent on the consistency of ZFC; further, PROOF is clearly NP, since proofs are checkable in polynomial time and the length of the proof to be guessed is linear in the size of the string of 1′s. Thus PROOF is NP-complete.

2) Assume ZFC proofs (that is, proving a theorem given the proof’s length in unary) are NP-complete. Then assume ZFC is inconsistent. Then we have that we can find a contradiction in ZFC in constant space and time. Further, every proposition in ZFC can be proved, and a proof can be found in polynomial time. So since ZFC proofs are NP-complete and also polynomial time, we have that P = NP. (If not enough space is available to generate the full proof of the contradiction in ZFC, we can still guess all possible proofs of the theorem in constant time and see if one of them works, since the proof allocated for the theorem must be shorter than the proof of the contradiction.)

3) This follows from the contraposition of the above (#2).

4)  Assume ZFC is consistent.  Then we have that “ZFC proofs are NP-complete,” (see step one), and that “ZFC proofs are NP-complete –> (P != NP –> ZFC is consistent).”  Thus we get that our assumption implies “P != NP –> ZFC is consistent.”  So:  “ZFC is consistent –> (P != NP –> ZFC is consistent).”

Now let’s examine the statement “P != NP –> ZFC is consistent” by itself.  By Godel’s second incompleteness theorem, we have that ZFC is consistent cannot be proved within ZFC unless ZFC is inconsistent.  So if we had a proof that P != NP (in ZFC), then we would have a proof that ZFC is consistent, implying that ZFC is not consistent.  Thus, we can conclude that “(P != NP –> ZFC is consistent) –> (ZFC is consistent –> P != NP cannot be proved in ZFC).”

Above, we saw that “ZFC is consistent –> (P != NP –> ZFC is consistent).”  Just now, we saw that “(P != NP –> ZFC is consistent) –> (ZFC is consistent –> P != NP cannot be proved in ZFC).”  From these two statements, we can conclude:  “ZFC is consistent –> (ZFC is consistent –> P != NP cannot be proved in ZFC).”  This simplifies to:  “ZFC is consistent –> P != NP cannot be proved in ZFC.”

Posted in Uncategorized | 1 Comment

Proof that P != NP can never be proved (if ZFC is consistent)

[Updated:  01-26-2014]

After following the comments on the previous post, I became convinced that my last post–in which I claimed to have a proof that P != NP is true–is interesting but not sufficient to resolve P != NP.

If ZFC is consistent, P != NP cannot be proved true.

Please note that I am not a good logician; I’ve never had a course in formal logic, so I’m not that great.  Any feedback or other comments on my argument are welcome.

NOTE:  I cannot actually prove that P != NP cannot be proved true; however, I can prove that PROOFS is not in P.  See the other post I made for the correct argument.

Here is my argument:

1 – If ZFC is consistent, ZFC proofs are NP-complete.

2 – If ZFC proofs are NP-complete, then:  ZFC is inconsistent –> P = NP.

3 – If ZFC proofs are NP-complete, then:  P != NP –> ZFC is consistent.

4 – If ZFC is consistent, then P != NP cannot be proved in ZFC.

Proofs:

1.  If ZFC is consistent, then there exist both theorems and non-theorems of ZFC.  We can construct a proposition that is comprised of other variable propositions (e.g., “(prop1 ^ prop2 ^ !prop3) v (prop3 ^ prop4 ^ !prop5)”), and say that the proposition is “satisfiable” iff setting these propositions to concrete ZFC propositions yields something that is a theorem.  This satisfiability question should be easy to check, if each prop can be set to a ZFC proposition with either a very short proof or with no proof.  We can construct, for example, a Godel sentence to be an unprovable proposition (or the negation of a true proposition for that matter); we know that ZFC is consistent by our assumption, so constructing SAT instances is not hard.  This shows us that SAT is NP-complete.

2.  Assume ZFC proofs (that is, proving a theorem given the proof’s length in unary) are NP-complete.  Then assume ZFC is inconsistent.  Then we have that we can find a contradiction in ZFC in constant space and time.  Further, every proposition in ZFC can be proved, and a proof can be found in polynomial time.  So since ZFC proofs are NP-complete and also polynomial time, we have that P = NP.  (If not enough space is available to generate the full ZFC proof, we can still guess all possible proofs, since after a certain amount of proof space is made available the proof can be found using the method just described.)

3.  This follows from the contraposition of the above.

4.  Assume ZFC is consistent.  Then we have that “ZFC proofs are NP-complete,” (see step one), and that “ZFC proofs are NP-complete –> (P != NP –> ZFC is consistent).”  Thus we get that “P != NP –> ZFC is consistent.”  If there were a proof in ZFC that P != NP, we would get a proof that ZFC is consistent as a consequence; this violates Godel’s second incompleteness theorem.  Thus, if ZFC is consistent, P != NP cannot be provable (in ZFC).

Note:  We would of course also be interested in proving that “If ZFC is consistent, P = NP cannot be proven true in ZFC;” however, there is no clear way to achieve this that I can see.  If you have any ideas for a proof of this claim, please let me know what they are!  Perhaps there is a way to exploit the fact that P = NP does not relativize to show that P = NP cannot be proven true.  I am tempted to consider my previous wrong proof that P != NP as potentially useful in this endeavor.  In particular, we know that if P = NP, Step 3 can be proved false; that is, “diagNP is in EXP” and “diagNP is in EXP” does not relativize…can be proved true.  If we could somehow show that this is impossible, we could perhaps demonstrate that P = NP can never be proved.  This actually sounds plausible, since if “diagNP is in EXP” could be proved true, we would have that NP != EXP can be proved true.  If there were a way to establish that NP != EXP, like P != NP, can never be established in ZFC, we would have a complete proof that P = NP can never be proved.

Posted in Uncategorized | 1 Comment

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.

Posted in Uncategorized | 12 Comments