Math Update: My P != NP Proof Might Be Correct!!!!! -- (update, no it's not, see the note at the beginning and the updates near the bottom)
EDIT: No, this proof is not correct. See the updates at the bottom for details on why (based on Dr. Zelinsky's comment). Fortunately, my GLL proof and MSR proofs still appear to be correct.
It could be that Joshua Zelinsky's comment actually helps me to complete the proof.
The GLL proof appears to be correct, AFAIK.
The thing is, the fact that we can prove "PA is consistent --> P != NP" within PA and the fact that we can prove "PA is consistent" as a theorem of ZFC just shows that P != NP is a theorem of PA. That isn't a contradiction, it's just another step in the proof.
I think the striking idea is, P != NP is a theorem of PA, but not of ZFC. That is what I worked to prove. AFAIK it is possible for a proposition to be a theorem of PA but not of ZFC. In particular, PA can be proved consistent from ZFC, so we would think it s possible and even likely that there are some non-theorems of ZFC that are theorems of PA.
So this is great! It looks like I have 3 good results regarding P vs. NP: P != NP is not a theorem of ZFC, P != NP is a theorem of PA, and NP is a subset of BQP.
Dr. Joshua Zelinsky deserves credit for having written in the last line of the proof that P != NP is a theorem of PA. If CMI decides to award money for the solution, I don't object to JZ getting an appropriate share of the money.
Update:
I realized something important about this.
Aside from the quantum-computing-related proof, what we are actually able to prove is:
1 - P != NP cannot be proved as a theorem of PA/ZFC within PA/ZFC
2 - We have, as a theorem of ZFC, that P != NP is a theorem of PA
So in other words, we can prove in ZFC that PA has P != NP as a theorem, but we cannot actually prove that in PA itself. Fortunately, it does not yield a contradiction...ZFC has "P != NP is a theorem of PA" as a theorem, but, PA does not have "P != NP is a theorem of PA". It just so happens that ZFC can prove something that PA cannot prove, which is not all that unexpected...in particular, we can also prove "PA is consistent" is a theorem of ZFC but not of PA.
Another update:
One sort of philosophical and informal comment we could make about this is, "It is roughly true that 'PA is consistent' has the same 'logical power' as 'P != NP.'"
Another quick update:
By the way, the answer to the relativization challenge is, PROOFS_ZFC and PROOFS_PA are not NP-complete relative to oracles X such that P^X = NP^X . In particular, those two languages are not NP-hard relative to such oracles X.
Another quick update:
I think that PROOFS_ZFC and PROOFS_PA are also not NP relative to the oracles described above in the previous update. The reason is that relative to the oracle, there are sentences that can be written down "rather succinctly," particularly, sentences that are about the computations of Turing machines relative to the, e.g., PSPACE-complete-problem oracles, that cannot be proved to be correct in a "similarly succinct" way. Under the traditional "null oracle," we can prove sentences about Turing machines and their computations efficiently enough by exploring a computation history, to put it vaguely and informally. As soon as oracles are introduced, certain very succinct computations becomes PSPACE-hard in general to write out and prove the correctness of.
Another clarification:
In case this sounds suspicious, think of it written like this:
"P != NP is a theorem of PA" cannot be proved in PA
"P != NP is a theorem of PA" can be proved in ZFC
By the way, the reason I have confidence that my proofs are correct is, *I proofread my P != NP and GLL proofs repeatedly and wrote out every step and verified every sentence*, although I did it a long time ago and don't remember it. Note, I'm not a math Ph.D., so it is *possible* that I am wrong. I have not recently gone back and reviewed my proofs for accuracy.
One more thing:
The fact that P != NP is a theorem of PA can be proved in ZFC is a non-constructive proof. In particular, we do not have a full proof that P != NP in PA that can be written out. It is not quite the case that P != NP is logically equivalent to "PA is consistent," because PA is consistent is not a theorem of PA at all, whereas we are claiming that P != NP is a theorem of PA, but just one that we cannot find a proof of.
More comments:
If this proof is accepted as correct, and I personally see no mistake in it (although I'm not an authority or a true expert), it would appear to say something big about ZFC. In particular, although ZFC is likely consistent, it would appear that "ZFC hallucinates a proof of a theorem of PA that is not actually a theorem of PA." Thus, we would tend to believe that ZFC and ZF, while consistent, might not be sound, in particular. If there is indeed no proof that P != NP in PA, as is proved in PA, then the fact that ZFC seems to be able to prove that P != NP is a theorem of PA--that a proof does exist, even though we can never find one according to PA--suggests that there is a dispute between PA and ZFC, in a sense. It could be that the power set operation in ZFC is in some way "bad," and in need of removal...such a removal would drastically change how mathematicians interpret infinity.
The key is, the proof that "PA is consistent" would need to be made invalid in a new, modified version of the ZFC axioms. It needs to be the case that no formal theory that we consider sound and worth using can prove PA is consistent. I myself just read on the internet somewhere that PA is consistent can be proved as a theorem of ZFC...I don't know how that proof works.
Another update:
If the proof is wrong, and it might be, it's not the GLL proof that is wrong, but the main argument that "ZFC/PA is consistent --> P != NP" that is wrong. In other words, I'm more certain that the GLL proof is correct than I am that the other proof is correct. I am willing to do a little bit of mathematical thinking and writing, but I'm currently not interested in re-reading or re-checking any of my proofs. I am rather isolated, and am working on my mental health. I don't have that much to do, but I don't think it would be healthy or a good use of my time to re-read and re-check my old P vs. NP proofs (/proof attempts) right now.
I am claiming that GLL is "very likely correct," and, that my other proofs is "possibly correct and in a state of having been checked repeatedly and carefully before." If you want, evaluate the proofs yourself and/or consult with a friend who is an expert or a degree holder in math.
Another update:
Here is the link to the Reddit thread that has my proof linked to from it:
https://www.reddit.com/r/mathematics/comments/pdl71t/comment/nsug1zr/
I can't find a good version of my Godel's Lost Letter proof on comp.theory, but probably, an altered version of this incorrect proof could be spun into a formal proof that PROOFS is not in P is not a theorem of ZFC.
https://groups.google.com/g/comp.theory/c/sV96PQz2Qrg/m/lvbwat8cCgAJ
The basic argument for GLL is:
ZFC is inconsistent --> PROOFS is in P
PROOFS is not in P --> ZFC is consistent
ZFC_Provable(PROOFS is not in P) --> ZFC_Provable(ZFC is consistent)
! ZFC_Provable(PROOFS is not in P) (here, ! means "not")
If you believe me that the first line is true, the rest of the proof is simple.
Here's a direct link to the PDF of my other paper:
Another update:
No, sidewalk walker , I will not “slow down.” Bad monopoly deal, nothing in it for me.
Summary of logic:
Within ZFC:
PA is consistent
Within PA:
PA is consistent—> P != NP
Maybe the argument is that there is no logic result, because you can’t use modus ponens in ZFC on a theorem from PA. Maybe Godel numbers would somehow enable that though.
Another update:
Yeah false alarm about the logic. The true inferable insight about logic is: Not all theorems of PA are theorems of ZFC. Although PA is proved consistent, it is not proved sound within ZFC. Thus, PA is consistent—> P!= NP …is not a theorem of ZFC. That’s because if it were, then by modus ponens, P != NP would be a theorem of ZFC contradicting the GLL result.
Another update:
I am actually leaning towards thinking that the proof must be wrong. I think that actually, all theorems of PA are theorems of ZFC. If that's true, that means, my proof, which I haven't re-read recently, is wrong.
Fortunately, my other two proofs are very likely correct. GLL and MSR is in BQP.
Another update:
The fact that the proof is wrong shows that Dr. Zelinsky showed:
PA is consistent --> P != NP
...is not a theorem of PA if PA is consistent. If it were, then by modus ponens, we would violate the GLL proof.
So in other words, Dr. Zelinsky alluded to this proof:
PA is consistent --> ("PA is consistent --> P != NP" is not a theorem of PA)
In other words, the thing I'm trying to prove is not going to work at all, unless of course there's a ZFC proof of the target theorem but no corresponding PA proof. You would have to use the fact that it's ZFC to prove that it's PA, as Dr. Zelinsky said.
Comments
Post a Comment