Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

If loving linux is wrong, I dont wanna be right. -- Topic for #LinuxGER


devel / comp.lang.c / About a ℙ≠ℕℙ proof (v3.2)

SubjectAuthor
o About a ℙ≠ℕℙ proof (v3.2)wij

1
About a ℙ≠ℕℙ proof (v3.2)

<f5779fd6-a6fc-4918-a6d2-fc4b1654c189n@googlegroups.com>

  copy mid

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

  copy link   Newsgroups: comp.lang.c
X-Received: by 2002:a05:622a:8c8:b0:3a5:7de1:9708 with SMTP id i8-20020a05622a08c800b003a57de19708mr43701043qte.616.1669552415753;
Sun, 27 Nov 2022 04:33:35 -0800 (PST)
X-Received: by 2002:a37:d246:0:b0:6f6:e7d1:4d1f with SMTP id
f67-20020a37d246000000b006f6e7d14d1fmr41054745qkj.477.1669552415581; Sun, 27
Nov 2022 04:33:35 -0800 (PST)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.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: Sun, 27 Nov 2022 04:33:35 -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: <f5779fd6-a6fc-4918-a6d2-fc4b1654c189n@googlegroups.com>
Subject: About a ℙ≠ℕℙ proof (v3.2)
From: wynii...@gmail.com (wij)
Injection-Date: Sun, 27 Nov 2022 12:33:35 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 4043
 by: wij - Sun, 27 Nov 2022 12:33 UTC

Basic proof (using C-like notation):
Define: bool S(Prog,Arg): S(c,n)==true iff ∃x, c(x) returns true in P-time.

S is a language interpreter. Prog and Arg are pass-by-value arguments. E.g.
scripts, TM description, CNF evaluator,... and their possible solutions for
Prog to check.

From definition of S, S computes a problem in ℕℙ.
If Problem(S)∈ℙ, there exists a P-time Prog f defined as follow:
bool f(Arg x) {
return !S(f,x);
}

From Liar's paradox and the HP proof, f is an undecidable instance for S. And,
f and S cannot both be in the same P-time convertible set. Therefore, ℙ≠ℕℙ.

Note: The definition of S (and ℕℙ) only requires the certifying instance
"c(x)==true" run in P-time. Complexity of c itself is not an issue, c can even
never terminate. These 'timed-out' cases should return false, but the result of
the S(f,n) case always contradicts the definition of S.
QED.

Prog f exists in various forms, shown as a function specification to make the
basic proof succinct by avoiding lots of symbol/definition/axiom/lemma...coding issues stuff.
If the above is correct, then, we change to use 'executable' to demonstrate,
because 'executable' is easier to understand and VERIFIABLE by real TM.

// The folowing proves S2,f2 both exist in the language of a real TM.
Executable: S2 <prog> <uint>
Definition: The exit status of "S2 <prog> <uint>" is 1 iff there exists an
"p x" instance, where x<=n, and the exit status of "p x" is 1.

// From the specification, S2 can be built from such a C program (error checks
// are omitted).
//
int main(int argc, char* argv[]) { // main() takes exactly two arguments
const char* FuncName= argv[1]; // argv[1] is <prog>
const UInt MaxN= atoi(argv[2]); // convert argv[2] to UInt

for(Uint x=0; x<=MaxN; ++n) {
const char* cmd= make_cmd(FuncName,x); // make command string for system(..)
if(system(cmd)==1) { // exec: S2(f,x), may be assumed a pseudo-parallel
return 1; // system call to simulate NDTM
}
}
return 0;
}

// As S2 exists, an executable f2 can be built from such a C program (error checks are omitted).
//
int main(int argc, char* argv[]) {
const char* cmd= make_cmd("S2 f2 ", argv[1]); // make command string for system(..)
return !system(cmd); // exec: S2(f,n)
}

// After S2 and f2 are built, test with "S2 f2 8"
[] S2 f2 8 // execute from terminal
....
Aborted (core dumped) // infinite recursive call, expression of undecidability

-----------
I am not familiar with complexity theory. For such a proof to be really
convincing, one needs to explain existing ℕℙℂ examples as a double check and
possibly some others I may be unaware of. So, I should stop here and ask
question for possible flaws of this basic proof.

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor