2
$\begingroup$

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.

  • 0
    Just to be specific, whose question are you talking about?2011-01-10
  • 0
    Your third option does not really make sense. Can you make precise what you mean by the third possibility?2011-01-11
  • 1
    @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?"2011-01-12
  • 1
    @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.2011-01-12

2 Answers 2