ℙ!=ℕℙ proof

[wij]

This is the P!=NP proof revised from the previous one.

-------------
ANPC::= Set of decision problems that additional information c must
be provided to compute the problem in P-time (including 
processing the information c (certificate)).

Since the information c can be generated in O(2^N) time, the upper
bound of ANPC is O(2^N) (checking c is in P-time).

Corollary: ANPC ⊆ ℕℙ
(from ℕℙ definition: "... ℕℙ is the set of decision 
problems verifiable in polynomial time by a
deterministic Turing machine.
https://en.wikipedia.org/wiki/NP_(complexity)")

If we try to prove or show that an ANPC problem can be solved in P-
time, we would also be trying to prove/show that the requirement of
the additional information c is not necessary. Thus, such a proof
will just prove itself not a valid proof, IOW, ANPC==P is unprovable.

Conclusion: ANPC is not P-time provable/solvable (implied by
ANPC definition)

Corollary: ℕℙ!=ℙ (ANPC ⊆ ℕℙ AND ANPC!=ℙ)

------------
I had just read something about the P-NP problem again, the P-
NP problem is actually quite tricky and highly 'academic'. That is
why the proof was changed to using ANPC. This version of P!=NP
proof is easy to understand. But, sadly, it does not provide direct
insight as to why TSP (or other NPC graph problems) cannot be solved in
P-time. I think this part may be (I am not sure) explained by Cook-
Levin Theorem (The CNF-SAT problem might be provable in O(2^N)).

[immibis]

On 2/02/24 13:21, wij wrote:
> This is the P!=NP proof revised from the previous one.
>
> -------------
> ANPC::= Set of decision problems that additional information c must
> be provided to compute the problem in P-time (including
> processing the information c (certificate)).
>
> Since the information c can be generated in O(2^N) time, the upper
> bound of ANPC is O(2^N) (checking c is in P-time).
>
> Corollary: ANPC ⊆ ℕℙ
> (from ℕℙ definition: "... ℕℙ is the set of decision
> problems verifiable in polynomial time by a
> deterministic Turing machine.
> https://en.wikipedia.org/wiki/NP_(complexity)")
>
> If we try to prove or show that an ANPC problem can be solved in P-
> time, we would also be trying to prove/show that the requirement of
> the additional information c is not necessary. Thus, such a proof
> will just prove itself not a valid proof, IOW, ANPC==P is unprovable.

If you prove the additional information c is not necessary, then you
prove the problem is not an ANPC problem.

[wij]

That is correct. But, the way ANPC described does not look right,
maybe I should revert to using ANP.

The basic is the same: Devise a class, e.g. ANP (or ANPC, to avoid the
difficulty of 'conventional NP definition'). You may see the 
P-NP problem is actually a 'word game'.

[immibis]

All mathematical problems are 'word games'.