Sujet : Proof2: ℙ≠ℕℙ is released
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theoryDate : 18. Mar 2025, 11:58:36
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <52d8d45d0db77680236c09bb395148d8803f7f17.camel@gmail.com>
User-Agent : Evolution 3.54.3 (3.54.3-1.fc41)
This ℙ≠ℕℙ proof is the shortest one and easy to understand
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download...
+--------------+
| Proof2: ℙ≠ℕℙ |
+--------------+
STM::= Turing machine represented by string {0,1}* string
Num(x)::= Function that maps {0,1}* to natural numbers
Let s∈STM, s:STM->{0,1}. s is a function that computes a Turing machine
decision function in Ptime and is defined as follows:
s(f)=1 if ∃c∈<=Num(f), f(c)=1.
Therefore, Problem(s)∈ℕℙ (the problem solved by s is ℕℙ problem)
The proof of this assertion is quite straightforward and trivial, so it is
omitted. Doubts about whether certain natural numbers are legal Turing
Machines are not a problem, because the definition of ℕℙ does not consider
(and can handle) this situation.
Assume that Problem(s)∈ℙ holds, then by definition
s(s)=1 if ∃c∈<=Num(s), s(c)=1.
But when c=Num(s), there will be a self-referential situation where
s(s)=1 if s(s)=1 (similar to the undecidable situation of the halting
problem). Therefore, the assumption that ℙ=ℕℙ does not hold, that is, ℙ≠ℕℙ.