-2

Is $P=NP$ an $NP$-complete problem?

In other words, is it possible (and does it make any sense) to show that proving $P=NP$ (or $P\neq NP$) cannot be done in polynomial time?

I am not even sure it belongs to $NP$.

Kuifje
  • 9,584
  • 2
    I don't think it makes sense to ask about the complexity of a proof. Complexity pertains to algorithms. – xxxxxxxxx Oct 25 '15 at 14:25
  • @MorganRodgers I agree, but complexity also pertains to problems, no? – Kuifje Oct 25 '15 at 14:26
  • Is there a classification of problems that separates problems solved with algorithms from the rest? Not to my knowledge. Some problems can be solved with or without algorithms, e.g. finding an orthonormal basis in a Hilbert Space can be done with a Gram-Schmidt algorithm, or by reasoning with elementary algebra. – Kuifje Oct 25 '15 at 14:29
  • To prove that $P= NP$, it is sufficient to output an algorithm that solves an $NP$-complete problem in polynomial time, therefore we could imagine an algorithm that generates such a procedure. Or, the other way around, to prove that $P\neq NP$, it is sufficient to output a problem from $NP$ that is, "by construction", not possible to solve in polynomial time. One could imagine a procedure that generates such a problem. The polynomial variables would then be the complexity of such procedures. But I am just making suggestions…again I am not entirely convinced this whole thing makes any sense. – Kuifje Oct 25 '15 at 14:38
  • "We could imagine an algorithm that generates such a procedure" I think you are more imaginative than me :) – pjs36 Oct 25 '15 at 14:42

1 Answers1

4

I do not think that this question is meaningful. A proposed theorem is either true, false, undecidable, or has its truth not yet known (at least I think this is true).

I mean, replace "P = NP" with "the $\sqrt{2}$ is irrational", or the Riemann hypothesis, or the prime gap theorem or "all my answers on math.stackexchange.com are correct" (this last one is clearly false).

marty cohen
  • 107,799
  • So this suggests that not all problems (e.g. proving a theorem) are not all computational? That makes sense…and relates to Morgan Rodgers comment above. – Kuifje Oct 25 '15 at 14:43