Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

19 views

Skip to first unread message

Feb 3, 2024, 10:11:36 PMFeb 3

to

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. ------------

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. ------------

0 new messages

Search

Clear search

Close search

Google apps

Main menu