Sujet : Re: Improved ℙ≠ℕℙ proof
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theoryDate : 06. Jun 2024, 05:45:31
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <7628d0ddbfbe61abaec59f0ef77968b9f451d1e2.camel@gmail.com>
References : 1 2 3 4
User-Agent : Evolution 3.50.2 (3.50.2-1.fc39)
On Mon, 2024-06-03 at 23:04 +0800, wij wrote:
ℙ≠ℕℙ Proved.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download...[cut]
Note: Another super short proof that ℙ≠ℕℙ (might be less constructive).
Proof: If ℙ=ℕℙ, then ℕℙℂ=ℙ. All the problems in ℕℙ are Ptime reduciable.
That means all the proofs that prove "Decide whether or not a given
number is even" is not a ℕℙℂ are false proofs. Since such proofs are
considered valid, ℕℙℂ and ℙ is not the same, therefore, ℙ≠ℕℙ.
Improved ℙ≠ℕℙ proof
Re: Improved ℙ≠ℕℙ proof