principleMinor
Is the P vs NP problem, an NP or co-NP problem?
Viewed 0 times
problemthestackoverflow
Problem
A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way :
https://www.youtube.com/watch?v=YX40hbAHx3s
At 7 minutes and 56 seconds however, he talks about why it is so hard to prove that P $=$ NP or that P $\neq$ NP, and states that proving things is in fact an NP problem (in the video however, he writes down that it is actually a co-NP problem).
Thus, is proving things, in particular P $=$ NP or P $\neq$ NP, an NP or co-NP problem? If so, why? And where could I find more on this?
https://www.youtube.com/watch?v=YX40hbAHx3s
At 7 minutes and 56 seconds however, he talks about why it is so hard to prove that P $=$ NP or that P $\neq$ NP, and states that proving things is in fact an NP problem (in the video however, he writes down that it is actually a co-NP problem).
Thus, is proving things, in particular P $=$ NP or P $\neq$ NP, an NP or co-NP problem? If so, why? And where could I find more on this?
Solution
It isn't meaningful to say that a single specific question is in NP or any other complexity class. In order to classify things as being in P, or NP, or co-NP, etc. they need to be sets of problems with some parameter. So for example, the problem "Is the positive integer n prime" is a question where we can discuss this sort of thing.
In a certain overly pedantic sense, the correct answer to your question is that the problem you care about is in P, since there's an algorithm which will answer every question of your form in polynomial (in fact constant time). But we don't know if that algorithm is just "Return TRUE" or is "Return False."
The idea that the video may be touching on is the idea that if P != NP, then in general, finding proofs is hard. In fact, "Is statement S provable in formal system A with a proof of length at most x" is an NP-hard problem" (Questions in this are things like "Is there a proof of Fermat's Last Theorem that's shorter than 5 pages.") . And we also expect that if P != NP, for most "natural" NP-complete problems, random instances will often not be easy. So if P != NP, then searching for proofs should often be difficult, and thus we shouldn't be surprised that the proof that P != NP would itself be one of those. This may be what they were trying to say.
In a certain overly pedantic sense, the correct answer to your question is that the problem you care about is in P, since there's an algorithm which will answer every question of your form in polynomial (in fact constant time). But we don't know if that algorithm is just "Return TRUE" or is "Return False."
The idea that the video may be touching on is the idea that if P != NP, then in general, finding proofs is hard. In fact, "Is statement S provable in formal system A with a proof of length at most x" is an NP-hard problem" (Questions in this are things like "Is there a proof of Fermat's Last Theorem that's shorter than 5 pages.") . And we also expect that if P != NP, for most "natural" NP-complete problems, random instances will often not be easy. So if P != NP, then searching for proofs should often be difficult, and thus we shouldn't be surprised that the proof that P != NP would itself be one of those. This may be what they were trying to say.
Context
StackExchange Computer Science Q#112725, answer score: 6
Revisions (0)
No revisions yet.