3 ms·

My understanding is it's necessarily either true or false, but may not be provably true or false. This could allow us to actually have an algorithm that solves

My understanding is it's necessarily either true or false, but may not be provably true or false. This could allow us to actually have an algorithm that solves all NP problems in P time, but ZFC can't prove it works for all inputs. Edit: So in that case, what would it mean to add an axiom that P=NP? See https://mathoverflow.net/questions/50023/independence-of-p-np https://mathoverflow.net/questions/50023/independence-of-p-n... especially the answer by Andreas Blass. Basically, you could add axioms that change the meaning of 'Turing machine' (ie 'computation') by changing the meaning of 'natural number' resulting in an algorithm witnessing P=NP that maybe can't be run on physical computers. Way off topic...

hansvm 6y ago
Agreed, definitely off topic. Fun to consider anyway :) Without considering many facts specific to P=NP, it could be feasible for it to neither true nor false in ZFC (i.e., some model of ZFC has P=NP, and some other has P!=NP), in which case you could take P=NP as another axiom. Other statements that work this way include the continuum hypothesis. If I'm not mistaken (and misstatements regarding P=NP are common, so don't take this blindly), P=NP has a substantial amount of additional structure to it due to it being a low-complexity arithmetical statement. In particular, I believe you're correct that in ZFC it is actually either true or false in all models, but not necessarily provably so from within ZFC. In this case you could try to take it as an axiom (e.g. ZFC+PNP), but you'd either wind up with ZFC itself or an inconsistent axiom set. As a related (maybe equivalent?) statement, P=NP has the property that if A is an axiom independent from ZF and P=NP (resp P!=NP) is provable in ZF+A then P=NP (resp P!=NP) is provable in ZF, again due to its nature as a low-complexity arithmetical statement, so either P=NP is unprovable in any meaningful extension of ZF, or it's provable in all of them.

hansvm 6y ago

Agreed, definitely off topic. Fun to consider anyway :) Without considering many facts specific to P=NP, it could be feasible for it to neither true nor false in ZFC (i.e., some model of ZFC has P=NP, and some other has P!=NP), in which case you could take P=NP as another axiom. Other statements that work this way include the continuum hypothesis. If I'm not mistaken (and misstatements regarding P=NP are common, so don't take this blindly), P=NP has a substantial amount of additional structure to it due to it being a low-complexity arithmetical statement. In particular, I believe you're correct that in ZFC it is actually either true or false in all models, but not necessarily provably so from within ZFC. In this case you could try to take it as an axiom (e.g. ZFC+PNP), but you'd either wind up with ZFC itself or an inconsistent axiom set. As a related (maybe equivalent?) statement, P=NP has the property that if A is an axiom independent from ZF and P=NP (resp P!=NP) is provable in ZF+A then P=NP (resp P!=NP) is provable in ZF, again due to its nature as a low-complexity arithmetical statement, so either P=NP is unprovable in any meaningful extension of ZF, or it's provable in all of them.