Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

%DCL-MEM-BAD, bad memory VMS-F-PDGERS, pudding between the ears


devel / comp.lang.c / A ℙ≠ℕℙ proof for review (v1.0)

SubjectAuthor
o A ℙ≠ℕℙ proof for review (v1.0)wij

1
A ℙ≠ℕℙ proof for review (v1.0)

<c68f58a3-fdda-44d8-86f9-aef41c7486a2n@googlegroups.com>

  copy mid

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

  copy link   Newsgroups: comp.lang.c
X-Received: by 2002:ae9:e604:0:b0:6fc:b0ff:b790 with SMTP id z4-20020ae9e604000000b006fcb0ffb790mr3229868qkf.350.1670004707521;
Fri, 02 Dec 2022 10:11:47 -0800 (PST)
X-Received: by 2002:a05:6214:3487:b0:4c6:9f78:6fc0 with SMTP id
mr7-20020a056214348700b004c69f786fc0mr47945203qvb.38.1670004707335; Fri, 02
Dec 2022 10:11:47 -0800 (PST)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c
Date: Fri, 2 Dec 2022 10:11:47 -0800 (PST)
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN
NNTP-Posting-Host: 124.218.76.41
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c68f58a3-fdda-44d8-86f9-aef41c7486a2n@googlegroups.com>
Subject: A ℙ≠ℕℙ proof for review (v1.0)
From: wynii...@gmail.com (wij)
Injection-Date: Fri, 02 Dec 2022 18:11:47 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2598
 by: wij - Fri, 2 Dec 2022 18:11 UTC

Using C-like notation:

ℙ::= Set of decision problem which can be computed by TM in P-time.

ℕℙ::= Set of decision problem q of which the positive answer can be verified by
a certificate c. I.e. a decision function v(q,c) yields true in P-time.

Spec: Function "bool S(Prog,UInt)" decides whether or not the argument Prog
program (equal-powerful as TM) is satisfiable in the range specified by UInt,
and the algorithmic steps is bounded by a given polynomial formula P. IOW:
S(f,n)==true iff ∃v,x, x<=n, v(f,x) proves f(x)==true (e.g. v simulates f(x))
and Time(v(f,x))<=P(|f|+|x|) proves a P-time certificate.

From the specification, Problem(S)∈ℕℙ (precisely, ℕℙℂ).
S can be implemented by a DTM. And, a Prog u of which the function is defined as
follow will also exist (The implement of u is very different. The implement of S
and u as existence proof are omitted, because they are supposedly understood
immediately):

bool u(UInt x) {
return !S(u,x);
}

From Liar's paradox and the HP proof, u is a never-terminating (undecidable)
instance. If S(u,n) computes in greater than P time, the answer S(u,n)==false is
fine. But, if S is in P time, u(x) can be in P time, then, the only condition
for S to return false in this case is u(x)==false which will not happen..
P-time S is unimplementable. Therefore, Problem(S)∉ℙ, ℙ≠ℕℙ.
QED.

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor