= 27d567bc2d48d9f40e9ccc20ea370b15)
Eliezer_Yudkowsky comments on When does an insight count as evidence? - Less Wrong
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 (37)
This isn't to be said casually; it would be a huge result if you could prove it, and very different from the case of neither being provable. Most things that are true about the natural numbers are not provable in any given set of axioms.
I mention this because I read that and woke up and said "What? Really?" and then read the following parenthetical and was disappointed. I suggest editing the text. If we don't know anything in particular about the relation of P=NP to set theory, it shouldn't be said.
Also, alexflint, you mean "negation", not "converse".
I've heard either that P = NP is known to be falsifiable or that its negation is. I don't remember which I heard.
I'm not quite sure what you mean by this. Falsifiable isn't really a word that makes sense in mathematics. P = NP is clearly falsifiable (give a proof that P!=NP) as is it's negation (give a polynomial time algorithm for an NP complete problem),
Scott Aarsonson has a paper summarising the difficulties in proving whether or not the P vs. NP question is formally independent of the Zermelo Fraenkel axioms: Is P vs NP Formally Independent (PDF file)
The paper is (obivously) pretty technical , but the take-home message is contained n the last sentence:
So I’ll state, as one of the few definite conclusions of this survey, that P = NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.
Sure it makes sense. Something is falsifiable if if it is false, it can be proven false. It's not obvious, given that P != NP, that there is a proof of this; nor is it obvious, given that P = NP, that for one of the polynomial-time algorithms for an NP-complete problem, there is a proof that it actually is such a thing. Though there's certainly an objective truth or falsehood to P = NP, it's possible that there is no proof of the correct answer.
Isn't this true of anything and everything in mathematics, at least in principle? If there is "certainly an objective truth or falsehood to P = NP," doesn't that make it falsifiable by your definition?
It's not always that simple (consider the negation of G).
(If this is your first introduction to Gödel's Theorem and it seems bizarre to you, rest assured that the best mathematicians of the time had a Whiskey Tango Foxtrot reaction on the order of this video. But turns out that's just the way it is!)
I know they get overused, but Godel's incompleteness theorems provide important limits to what can and cannot be proven true and false. I don't think they apply to P vs NP, but I just note that not everything is falsifiable, even in principle.