A ℙ≠ℕℙ Proof for improvement (v3)

[wij]

Using C-like notation:
Define: ℙ={f| f is a decision function that can be performed by a DTM in P-time}
Define: ℕℙ={f| f is a decision function that "f(x)==true" iff there exists an
instance c(d)==true,c∈ℙ}

note: The interpretation of 'ℕℙ', thus the definition, can be subtle in detail. If the ℕℙ is not equivalent to what is supposed, the explanation why the
above are not equivalent in solving the ℙ-ℕℙ issue will be very helpful.

Define: bool pchk(UInt psw): pchk is a P-time password checking function.
Define: bool Sat(Func, UInt): Sat(f,n)==true iff ∃x, x<=n, f∈ℙ, f(x)==true.

Question: Because Sat(f,n)==true, by definition, ∃x, x<=n, f∈ℙ, f(x)==true.
Therefore, Sat∈ℕℙ? // if Sat∈ℕℙ, Sat∈ℕℙℂ.
1. If Sat∈ℙ, this leads to a P-time password cracking function (we can find an
instance x, pchk(x)==true, by a binary search algorithm).
In addition, Sat also suffers from the Liar's Paradox problem. If Sat∈ℙ,
there exists cases Sat cannot decide (this is fine if Sat∈ℕℙ).
2. If Sat∉ℕℙ, this contradicts the definition of ℕℙ.

I am not familiar with TM language and complexity theory. But the more I get
involved into this issue (through some easier NPC examples), the more I
believe ℙ≠ℕℙ can be thus succinctly proved. Anything missed?

[Ben Bacarisse]

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

> Using C-like notation:
> Define: ℙ={f| f is a decision function that can be performed by a DTM in P-time}
> Define: ℕℙ={f| f is a decision function that "f(x)==true" iff there exists an
> instance c(d)==true,c∈ℙ}
>
> note: The interpretation of 'ℕℙ', thus the definition, can be subtle
> in detail. If the ℕℙ is not equivalent to what is supposed, the
> explanation why the above are not equivalent in solving the ℙ-ℕℙ issue
> will be very helpful.

Really? You've ignored all my previous posts pointing out the
"headline" reason why your ℙ and ℕℙ are not the P and NP of complexity
theory.

--
Ben.