Welcome to novaBBS (click a section below) |
mail files register newsreader groups login |

Message-ID: |

Subject | Author |

ℙ≠ℕℙ proof | wij |

1 |

<43a11c80b9826569e59c5f4774d512c1b8ba4a94.camel@gmail.com>

https://www.novabbs.com/devel/article-flat.php?id=3114&group=comp.lang.c%2B%2B#3114

Path: i2pn2.org!i2pn.org!news.nntp4.net!news.hispagatos.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail

From: wynii...@gmail.com (wij)

Newsgroups: comp.lang.c++

Subject: ℙ≠ℕℙ proof

Date: Sun, 04 Feb 2024 11:11:23 +0800

Organization: A noiseless patient Spider

Lines: 39

Message-ID: <43a11c80b9826569e59c5f4774d512c1b8ba4a94.camel@gmail.com>

MIME-Version: 1.0

Content-Type: text/plain; charset="UTF-8"

Content-Transfer-Encoding: quoted-printable

Injection-Info: dont-email.me; posting-host="bb4a5437f76966357d09782ee3bfe7bc";

logging-data="3688852"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/00Gd6KoLiad62moFS0OL8"

User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)

Cancel-Lock: sha1:hz5CJh0A+OAsTGgxsVEe6CKLAkI=

by: wij - Sun, 4 Feb 2024 03:11 UTCFrom: wynii...@gmail.com (wij)

Newsgroups: comp.lang.c++

Subject: ℙ≠ℕℙ proof

Date: Sun, 04 Feb 2024 11:11:23 +0800

Organization: A noiseless patient Spider

Lines: 39

Message-ID: <43a11c80b9826569e59c5f4774d512c1b8ba4a94.camel@gmail.com>

MIME-Version: 1.0

Content-Type: text/plain; charset="UTF-8"

Content-Transfer-Encoding: quoted-printable

Injection-Info: dont-email.me; posting-host="bb4a5437f76966357d09782ee3bfe7bc";

logging-data="3688852"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/00Gd6KoLiad62moFS0OL8"

User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)

Cancel-Lock: sha1:hz5CJh0A+OAsTGgxsVEe6CKLAkI=

This file is intended a proof that ℙ≠ℕℙ.

https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof.txt/download

-------------

ANPC::= Set of decision problems that additional information c must be

provided

to compute the problem in P-time (including processing the

information c

(certificate)).

Since the information c can be generated in O(2^N) time, the upper

bound of

ANPC is O(2^N) (checking c is in P-time).

Corollary: ANPC ⊆ ℕℙ (from ℕℙ definition: "... ℕℙ is the set of

decision

problems verifiable in polynomial time by a deterministic Turing

machine. https://en.wikipedia.org/wiki/NP_(complexity)")

If we try to prove or show that an ANPC problem can be solved in P-

time, we

would also be trying to prove/show that the requirement of the

additional

information c is not necessary. Thus, such a proof will just prove

itself not a valid proof, IOW, ANPC==P is unprovable.

Conclusion: ANPC is not P-time provable/solvable (implied by ANPC

definition)

Corollary: ℕℙ!=ℙ (ANPC ⊆ ℕℙ AND ANPC!=ℙ)

QED. ------------

1 |

clearnet tor