This file is intended a proof that =E2=84=99=E2=89=A0=E2=84=95=E2=84=99.=
=20
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof.txt/downlo=
ad
-------------
ANPC::=3D 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 =E2=8A=86 =E2=84=95=E2=84=99 (from =E2=84=95=E2=84=99 defin= ition: "... =E2=84=95=E2=84=99 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=20
would also be trying to prove/show that the requirement of the
additional=20
information c is not necessary. Thus, such a proof will just prove
itself not a valid proof, IOW, ANPC=3D=3DP is unprovable.
Conclusion: ANPC is not P-time provable/solvable (implied by ANPC
definition)
Corollary: =E2=84=95=E2=84=99!=3D=E2=84=99 (ANPC =E2=8A=86 =E2=84=95=E2=84=
=99 AND ANPC!=3D=E2=84=99)
QED. ------------=20
--- MBSE BBS v1.0.8.4 (Linux-x86_64)
* Origin: A noiseless patient Spider (3:633/280.2@fidonet)