Proof2: ℙ≠ℕℙ is released

Liste des GroupesRevenir à theory 
Sujet : Proof2: ℙ≠ℕℙ is released
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theory
Date : 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, ℙ≠ℕℙ.


Date Sujet#  Auteur
18 Mar 25 o Proof2: ℙ≠ℕℙ is released1wij

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal