About a ℙ≠ℕℙ proof (v3)

[wij]

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)
}

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.

[Jeffrey Rubard]

"I think you should read more about P and NP."

[Ben Bacarisse]

wij <wyni...@gmail.com> writes:

> 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 has parameters that are never referenced in the "body" of S. Since
you refer to c and n, you could just use those as the parameters. Or
you could use Prog and Arg in the definition.

∃c(x) has no conventional meaning. I am not sure, but I think you mean
something like

Exists c such that for all x, |x|<=|n| and c(x) returns true in P-time

but that's just a guess. "c(x) returns true in P-time" is only
meaningful when x is unbounded so the |x| <= |n| makes it nonsense.

> 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.

The last is not like the others!

> From definition of S, S computes a problem in ℕℙ.

The definition is currently nonsense, so it's hard to be sure, but then
"computing problem" is also nonsense so maybe it does not matter.

> If Problem(S)∈ℙ, there exists a P-time Prog f defined as follow:
> bool f(Arg x) {
> return !S(f,x);
> }

Too much to comment on now.

> I am not familiar with complexity theory.

Would it not be worth your while changing this fact?

--
Ben.