Sujet : Re: Improved ℙ≠ℕℙ proof
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.lang.cDate : 06. Jun 2024, 06:42:41
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <71791c32465a478dd7d8d278dc2c4680b894c4c3.camel@gmail.com>
References : 1 2 3
User-Agent : Evolution 3.50.2 (3.50.2-1.fc39)
On Mon, 2024-06-03 at 23:06 +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
