0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A decision problem with finitely many valid instances is automatically in P. Indeed, it can be solved in constant time. $\endgroup$ – Yuval Filmus Dec 14 '19 at 7:48
  • $\begingroup$ 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". $\endgroup$ – gnasher729 Dec 14 '19 at 13:31
  • $\begingroup$ @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. $\endgroup$ – Ryoji Dec 15 '19 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.