wij
unread,Nov 27, 2022, 7:33:43 AM11/27/22You do not have permission to delete messages in this group
Sign in to report message
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
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.