4 ms·
Is it possible to prove that a proof exists for either P=NP or P!=NP? Conversely, is it possible to prove that the conjecture is unprovable?
by kibwen 7y ago
Is it possible to prove that a proof exists for either P=NP or P!=NP? Conversely, is it possible to prove that the conjecture is unprovable?
- throwawaymath 7y agoYes, and yes. P != NP could be independent from Peano Arithmetic (PA) or the Zermelo-Fraenkel set theory with Axiom of Choice (ZFC) models. That is a separate conjecture which is also presently open.
- lidHanteyk 7y agoSurprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem. > At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't! [0] https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
- marcosdumay 7y agoSince an algorithm for running NP-complete problems in P-time would be enough to prove whether P=NP, wouldn't the impossibility to prove it just prove that P!=NP?
- H8crilA 7y agoNot really, we don't know if human reasoning is contained in P, BPP, BQP, PP or even PSPACE (is there a ghost in this shell?). It may not be. Though human reasoning probably is contained in P, just like probably P != NP.
- lonelappde 7y agoHuman reasoning is constant time. Generalized unbounded humanlike reasoning might not be.
- bloak 7y agoYou could perhaps have a program that for every input you've tried gives the correct answer in polynomial time, but you haven't yet proved that it always will. Nevertheless, I don't see how the answer to P!=NP could depend on the choice of axioms for set theory. Programs, their inputs and the state of a machine after executing n steps can all be encoded as integers, so P!=NP can be expressed as a statement about integers, and we know what the integers are: we don't need any dodgy set theory axioms for that. If that's wrong, someone please explain how. There are lots of interesting unsolved questions about integers (Goldbach's conjecture, ...) but people don't usually suggest that the answer to those questions might depend on the Axiom of Choice. Or do they?
- ookdatnog 7y agoSurprisingly, a theorem being unprovable does not mean that the theorem is untrue, even if you can prove its unprovability! This was shown by Goedel (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...). He showed that there exists no system powerful enough to express theorems about the natural numbers which can prove all facts about natural numbers and be sound (ie not prove things that are untrue).
- marcosdumay 7y agoThat's not exactly what I'm saying. What I am saying is that it's impossible for it to be true and unprovable. If it is true, it means a proof exists. Also, I am talking about this specific problem.
- lonelappde 7y agoCan you prove that? "impossibility to prove" is different from "proven impossible" because hiding behind the loose English are different models of logics. That's what Godel theorems at e about.
- tromp 7y agoIt is possible to be true and unprovable. Truth does not imply provability (the reverse does hold). Gödel's statement, which essentially says "I am unprovable" is an example of a true, unprovable statement.
- hinkley 7y agoWhen people try to use 'NP complete' as a dodge for doing difficult coding at work, I point out to them that Claude Shannon proved that generalized compression algorithms can't exist, and yet we are surrounded all day by compression algorithms. Just because the space in NP hard doesn't mean that your problem is automatically NP hard. Lots of human consumable or generated data is full of patterns that can be exploited to useful purpose, even when purely random inputs are intractable.
- gield 7y ago>[...] I point out to them that Claude Shannon proved that generalized compression algorithms can't exist [...] What proof are you talking about?
- kevinventullo 7y agoThey just mean that there is no general way to compress an arbitrary M-bit string to an N-bit string for M > N, and yet compression algorithms exist. The point is that the input to your compression is not an arbitrary M-bit string, but some very structured thing which could have a smaller representation. Similarly, when encountering what appears to be an NP-hard problem in the wild, you might still be able to find an efficient solution by exploiting the structure of your input (NP-hardness only applies when considering all inputs).
- areyousure 7y agoOne major issue is that the quote seems entirely backwards. In fact, Claude Shannon described how to optimally compress a string from a known source. https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theo... As such, Shannon's results would suggest the existence of many compression algorithms. (And conversely, I see no reason to believe that "Claude Shannon proved that generalized compression algorithms can't exist". I assume that result predates Shannon.)
- 7y ago