wij
unread,Nov 25, 2022, 7:41:00 AM11/25/22You do not have permission to delete messages in this group
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 ∃c(x), |x|<=|n|, 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 case for S. And, f and
S cannot both be in the same P-time convertible set. Therefore, ℙ≠ℕℙ.
QED.
Prog f exists in various forms, shown as a 'function' 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.
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 spec, S2 can be built in this 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)
return 1;
}
}
return 0;
}
// As S2 exists, an executable f2 can be built in this 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 undecidable)
----------------
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.
I'd like to know C++ programer's idea for such proof. If you insist a "C++"
question. You can say , e.g. "Confirmed, C++ program has no way to prove N==NP"