# P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.

And since if we prove that any problem in NP is a P that would mean that we have NP=P.

So by that logic either NP==P or it can never be proven that NP is not P and if somebody proves that, then won't they be contradicting the result itself. I mean they solved one NP problem which was this proof so by that logic all other problems should now be in class P.

Let me know if I got something wrong here.

And I found out that proving P Vs NP is an NP problem.

I think the two different meanings of the word "problem" are mixed here. When we discuss P and NP, they are the class of decision problems, which are essentially maps from the set of bits sequence to boolean values. On the other hand, "NP =/= P" is a long standing mathematical problem (general meaning,) but "NP =/= P" itself is a single proposition, and usually it's not considered as decision problem.

If you convert "NP =/= P" to a decision problem as the map from single point to true/false (this is completely valid formalization), its complexity is constant time (algorithm can simply return true or false, though we don't know which one is correct,) so it's in P and NP.

if somebody proves that, then won't they be contradicting the result itself

Proving "NP =/= P" means we know the correct return value in the algorithm above, and that doesn't contradict with anything. The result simply claims there is a NP problem that is not P. The decision problem "NP =/= P" is just an instance within class P. Both facts can hold simultaneously.

• A decision problem with finitely many valid instances is automatically in P. Indeed, it can be solved in constant time. – Yuval Filmus Dec 14 '19 at 7:48
• So given the question "is there a proof that P = NP" I can give the correct answer in constant time. The problem is that I don't know (and nobody currently knows) whether the correct answer is "Yes" or "No". – gnasher729 Dec 14 '19 at 13:31
• @YuvalFilmus gnasher729 Thanks for pointing that. I had the impression that the algorithm has to reach the answer without given knowledge on which is correct. I edited that part and described that the complexity is constant time. – Ryoji Dec 15 '19 at 1:14