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:
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.
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.
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?
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.
Posted By GASARCH to Computational Complexity
at 9/03/2009 11:58:00 AM