3 ms·
Since 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!=N
by marcosdumay 7y ago
Since 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.