• =?UTF-8?B?QWJvdXQgYSDihJniiaDihJXihJkgcHJvb2YgKHYzLjIp?=

    From wij@21:1/5 to All on Sun Nov 27 04:45:15 2022
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)