A stupid question from a dilettante… Does this avenue of research promise to eventually be able to assign probabilities to interesting statements, like whether P=NP or whether some program halts, or whether some formal system is self-consistent?
Promise? No. Might it start down an avenue that someday leads there after a whole lot more work and some additional ideas? Maybe. Don’t hold your breath on that P!=NP formal probability calculation.
Maybe I’m misunderstanding here, but it seems like we have no particular reason to suppose P=NP is independent of ZFC. Unless it is independent, its probability under this scheme must already be 1 or 0, and the only way to find out which is to prove or disprove it.
I think shminux is talking about the possibility of future research addressing bounded reasoners, who could be uncertain of P=NP even if it followed from ZFC.
While set theory already does that within forcing language (kinda, truth values are in a boolean algebra instead of a ring) for CH, AC, etc., the values of P!=NP cannot be changed if the models have the same ordinal (due to Shoenfield’s absoluteness theorem). I really hope that Probabilistic Set Theory works out, it seems very interesting.
A stupid question from a dilettante… Does this avenue of research promise to eventually be able to assign probabilities to interesting statements, like whether P=NP or whether some program halts, or whether some formal system is self-consistent?
Promise? No. Might it start down an avenue that someday leads there after a whole lot more work and some additional ideas? Maybe. Don’t hold your breath on that P!=NP formal probability calculation.
Hey, a man can hope. Interesting how it used to be physics driving the progress in math, and lately it’s been computer science.
This comment is a grossly oversimplified perspective, I think.
Maybe I’m misunderstanding here, but it seems like we have no particular reason to suppose P=NP is independent of ZFC. Unless it is independent, its probability under this scheme must already be 1 or 0, and the only way to find out which is to prove or disprove it.
I think shminux is talking about the possibility of future research addressing bounded reasoners, who could be uncertain of P=NP even if it followed from ZFC.
I fully agree that is an interesting avenue of discussion, but it doesn’t look much like what the paper is offering us.
http://www.academia.edu/1126434/IT_IS_UNLIKELY_THAT_P_NP_IS_INDEPENDENT_OF_ZFC
… Or a probability for the continuum hypothesis, axiom of choice, et cetera, if the probabilistic set theory works out. :)
While set theory already does that within forcing language (kinda, truth values are in a boolean algebra instead of a ring) for CH, AC, etc., the values of P!=NP cannot be changed if the models have the same ordinal (due to Shoenfield’s absoluteness theorem). I really hope that Probabilistic Set Theory works out, it seems very interesting.