Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login


U X e dUdX, e dX, cosine, secant, tangent, sine, 3.14159...

devel / comp.lang.c++ / ℙ≠ℕℙ proof

o ℙ≠ℕℙ proofwij

ℙ≠ℕℙ proof


  copy mid

  copy link   Newsgroups: comp.lang.c++
From: (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: <>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Info:; posting-host="bb4a5437f76966357d09782ee3bfe7bc";
logging-data="3688852"; mail-complaints-to=""; 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 UTC

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

ANPC::= Set of decision problems that additional information c must be
to compute the problem in P-time (including processing the
information c

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
problems verifiable in polynomial time by a deterministic Turing

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

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

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

devel / comp.lang.c++ / ℙ≠ℕℙ proof


rocksolid light 0.9.81
clearnet tor