Thursday, September 03, 2009

Is P=?NP ind of ZFC a respectable viewpoint?

I recently got an email that told me there is a debate going on about whether the the position P=?NP is independent of an axiom system such as ZFC deserves its own section on the Wikipedia P=?NP page. This raises several questions:
  1. Math Question: Is P=?NP ind of ZFC? I tend to think that P=?NP can be resolved in ZFC. My (possibly naive) reasoning is that P=?NP is a question about rather concrete objects, as opposed to CH which deals with the reals. This is not a strong believe on my part and I would like to see more serious arguments for and against.
  2. Sociology Question: Are there any serious CS theorists who believe that P=?NP is ind of ZFC? Of course this question depends on your definition of serious, theorist, and believe. Also it might not be the right question since, if (say) Terry Tao or Saharon Shelah thought that P=?NP was ind of ZFC then that is to be taken seriously, even though they are not CS theorists.
  3. An Infinite Number of Sociology Questions: For all i what is the strongest theory Ti such that there exists a set of i serious CS theorists, each one of them believing that P vs NP is ind of Ti?
  4. Wikipedia Question: How does Wikipedia decide these things? I do not know. However, if there was a credible paper saying why it is plausible that P=?NP might be ind of set theory, then I think it should be included. I do not know of any.
at

9 comments:

  1. Unknown1:21 PM, September 03, 2009

    Schoenfield Absoluteness gives some limitation. In particular, since P=NP is definable in PA, it is Delta^1_1, and thus absolute for all inner models of ZF+DC (and, a fortiori, ZFC). So there are quite a lot of forcing constructions that cannot prove it independent.

    I'm sure Harvey Friedman has thought about whether a large cardinal extension could change the truth of P=NP, but I don't remember hearing any results.

    ReplyDelete
  2. I.1:44 PM, September 03, 2009

    If P!=NP is independent of Peano Arithmetic, then "almost" P=NP. This is a simple argument, and the proof is in: http://www.cs.technion.ac.il/~shai/ph.ps.gz

    (Ben-David, S., and Halevi, S., "On the Independence of P versus NP", Technion, TR 714, 1992.)

    I.

    ReplyDelete
  3. D. Eppstein1:45 PM, September 03, 2009

    This is my fault, I think — someone was trying to make a separate section in the Wikipedia article on P vs NP and I cut it back.

    My opinion is here: it should be mentioned in the article, but not out of proportion to its importance to mainstream complexity theorists. So I am also interested in the answer to your sociology question.

    ReplyDelete
  4. Jeremy H1:59 PM, September 03, 2009

    Scott Aaronson has a nice survey and discussion on the topic.
    http://scottaaronson.com/papers/pnp.pdf

    ReplyDelete
  5. Greg Kuperberg2:13 PM, September 03, 2009

    Without knowing anything, it is respectable to ask whether P vs NP independent of ZFC. There are plenty of standard questions in mathematics for which it's not all that respectable, because the motivations are clear evidence that it isn't. Independence from ZFC can be viewed as the math student's version of the Anthropic Principle. But complexity theory is a fellow traveller of logic, so it's a little different.

    That said, it sounds like if you do know something, there is significant evidence that it isn't independent of ZFC. So the right thing to do in Wikipedia is to explain that evidence.

    ReplyDelete
  6. Mihai5:04 PM, September 03, 2009

    Marginally related: I remember a conversation with a friend from a while back..

    "You cannot dismiss this right away. Some serious mathematicians worked on it."

    "Well, yes, but they weren't serious when they did it."

    ReplyDelete
  7. B.6:46 AM, September 04, 2009

    Is P=?NP a simple mathematical question? That is, if for example someone proves that P=?NP is ind. of ZFC, is the problem solved? Because it remains interesting to know if there exists a polynomial algorithm for SAT (for example).

    ReplyDelete
  8. François G. Dorais9:00 AM, September 04, 2009

    It's also relevant to ask set theorists what they think! Because of the arithmetical nature of P vs NP, I think that an overwhelming majority would say that it is not a question of major interest to set theory (that is, of interest beyond its general importance in all of mathematics). However, there are two counterpoints to this.

    First, the methods of set theory are not necessarily irrelevant. For example, the relativization results of Baker, Gill, and Solovay (the last being a major figure in set theory) were inspired by forcing. However, this is not relevant to the independence of P = NP from ZFC.

    Second, the large cardinal hierarchy is a standardized benchmark for measuring the consistency strength of strong theories. If P = NP turns out to have such strength, then fitting it in this hierarchy becomes a very interesting question. However, there is currently no evidence that P = NP has such strength.

    ReplyDelete
  9. Igor Carboni10:19 AM, September 04, 2009

    There is recent paper from two brazilian logicians on the independence of P vs NP:

    COSTA, N. C. A. ; DORIA, F. A. ; BIR, E. . On the Metamathematics of the P vs. NP question. Applied Mathematics and Computation, v. 189, p. 1223-1240, 2007.

    I would like to know if someone has read this paper and what are the opinions about it.

    ReplyDelete