= 27d567bc2d48d9f40e9ccc20ea370b15)
orthonormal comments on What independence between ZFC and P vs NP would imply - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (62)
If ZFC and P vs NP are independent, this means that it's impossible to give a proof that P=NP with ZFC. Since an example of a polynomial-time algorithm that can solve an NP problem would be such a proof, any such algorithm must be impossible to state in ZFC. Any algorithm we can actually run can be stated in ZFC. As such, this would mean that P!=NP. You'd just have to prove it in ZFC+1, which is ZFC with the additional axiom that ZFC (the original, not ZFC+1) is consistent.
Exactly. For a more familiar example, the independence of the continuum hypothesis from ZFC means that we'll never stumble across a set of intermediate cardinality while doing an analysis problem (otherwise, we'd have a disproof), and so the CH is valid in a practical sense even though formally undecidable.
Generally speaking, if a statement is undecidable and claims the existence of something which could be effectively verified if it were found, then for practical purposes you can assume it's false.
EDIT: Oops- see paulfchristiano's comment on why P vs. NP isn't a case of this principle. I think the general principle is still OK, I just forgot about the whole "ability to effectively verify" bit in this case.
See paulfchristiano's comments. The mistake in DanielLC's comment is that, even though any polynomial algorithm can be "stated in ZFC", the proof that it runs in polynomial time doesn't necessarily lie within ZFC, or ZFC+Con(ZFC), or any other system you can name in advance.
Ah, thanks.