# What is the P versus NP question asking?

Is the P versus NP question asking "P = NP" or "ZFC |- P = NP" (or "|- P = NP" for that matter)? Because if I say P = NP, then I will be asked to prove it. But if the goal is "ZFC |- P = NP" then the result will not be useful because of the set theoretic assumptions of ZFC. So you may say the third choice matches our intuition, but it's not a (complete) question. If P = NP, then we are asked to prove |- P = NP and if P != NP we are not asked ~(|- P = NP) but |- P != NP. So what is the P versus NP question asking?

Actually this question can be asked for any question, it's not about P versus NP alone.

-
Just to be specific, whose question are you talking about? – Colin McQuillan Jan 10 '11 at 13:50
Your third option does not really make sense. Can you make precise what you mean by the third possibility? – Andrés Caicedo Jan 11 '11 at 2:15
@Andres Caicdo: I think lots of proofs in computer science do not require set theoretic axioms. This possibility reflects this fact. It basically says prove S or disprove S, leaving the gap that S is neither provable nor disprovable. But I think this is what the question asker has in mind when he says "Is P = NP?" – Zirui Wang Jan 12 '11 at 12:45
@Colin McQuillan: "Whose"? Sorry I don't get you. I'm just referring the famous question whether P = NP. I guess there is a consensus about what it means. – Zirui Wang Jan 12 '11 at 12:49

For the $1 million P vs NP prize, the Clay Mathematics Institute problem description does not even talk about proofs explicitly: Problem Statement. Does P = NP? http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf A proof is any completely convincing argument; set-theoretic foundations are just one tool that helps us study mathematical objects. - I think here "convincing" = "logical". And it's still not clear whether we can use the axioms of ZFC. – Zirui Wang Jan 10 '11 at 13:02 The test for C.M.I. is "general acceptance in the mathematics community". claymath.org/millennium/Rules_etc – Colin McQuillan Jan 10 '11 at 13:50 @Zirui: I think the mathematical and CS communities would be extremely surprised if the truth of P vs. NP turned out to depend delicately on our set-theoretic assumptions (e.g. if it were independent of ZF). Almost nobody expects this, and it would be a tremendous discovery. – Qiaochu Yuan Jan 10 '11 at 14:44 By$\vdash P = NP$, I'm going to assume that you mean you can only use the axioms of first-order logic (i.e., formulas that define the meanings of the logical symbols such as$\forall x(x = x)$for '=') and that "P = NP" is a shorthand for a formula in the language of arithmetic stating something nontrivial. In that case, P = NP is independent (of the axioms of first-order logic) but so is$0 = 1$. For the second formula, note that$0 = 1$is true in a model interpreting$0$and$1$as the same element and false in a model interpreting$0$and$1$as different elements. Therefore, we can neither prove it nor disprove it from the axioms of first-order logic alone. Specifically without axioms governing the interpretations of these symbols, we cannot derive any meaningful conclusions about whether P = NP. If you assume nothing, you can prove nothing! Therefore, you can be certain that the P versus NP problem does not ask for whether we can show$\vdash P = NP$but instead it asks whether$T \vdash P = NP$for some theory$T$enforcing the obvious rules we want to hold for arithmetic such as$0 \neq 1$. Moreover, it should be noted that the problem of P = NP has already been proven to be independent of certain weak theories of arithmetic. You can see a survey of the P = NP problem in http://www.scottaaronson.com/papers/pnp.pdf. The whole point is that independence results are less valuable when we assume less, and we cannot hope to prove$P = NP$or$P \neq NP\$ from a theory adequately representing its meaning without the theory being sufficiently powerful or inconsistent.