How do we know that the P versus NP problem is an NP problem itself?

Question

I have been doing some research on the P versus NP problem. On multiple occasions, I have seen people say that the problem itself is an NP problem. I have been curious about how we know this. If we know that the problem is NP, then has anyone come up with an algorithm that could be run on a nondeterministic Turing machine to solve the problem in polynomial time? Or is there some other reason that we know that the problem is NP?

Thanks for any replies in advance

Answer 1

Determining for any statement if there is a proof with $n$ symbols or less is an $NP$ problem (i.e. the proof can be checked in polynomial time with respect to the length of the proof and the statement), that's probably the sense in which they meant that "P versus NP is itself NP". However, it does not really make sense to assign a complexity class to proving any particular statement (such as $P\neq NP$), as that technically takes constant time.

Answer 2

The "P versus NP" problem is a single yes-no question: is $NP = P$? The correct answer is either "yes" or "no", we just don't know which. But the complexity of the answer is $1$.

Answer 3

While naïvely this statement makes little sense, there might be more to it than it seems.

This specific statement seems to be linked to the natural proofs barrier, one of several formal results (the so called barriers) on why it is so hard to proof $\smash{\mathrm P\not= \mathrm{NP}}$. Here is a great expository article on this:

• Timothy Y. Chow, "What is ... a natural proof?"

It starts as follows:

Have you ever wondered whether the reason there is (apparently) no simple proof that $\mathrm P\not= \mathrm{NP}$ is that $\mathrm P\not= \mathrm{NP}$? Or to turn it around, that an easy proof that $\mathrm P = \mathrm{NP}$ would somehow solve a problem that is hard not only in the Millennium Prize sense but also in the computational-complexity sense?

Stated this naïvely, the above idea does not quite make sense, but in a paper that won them the 2007 Gödel Prize, Alexander Razborov and Steven Rudich [3] proved a result that showed that there is something to this intuition after all. [...]