# 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

## 2 Answers

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.

Therefore, reasonable interpretations of the P = NP problem seem to suggest a proof from PA or ZFC. If you were to find that the problem were independent of one of these stronger theories, this would indeed be very significant. However, doing so using known techniques is essentially solving the problem itself as discussed in the following excerpt from Wikipedia:

These barriers have also led some computer scientists to suggest that the P versus NP problem may be independent of standard axiom systems like ZFC (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it's impossible to prove in ZFC that such algorithms are correct.[16] However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the Peano axioms (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.[17] Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

-