Re:A proof P = NP was accidentally published in TOCT
by RavlaAlvar on Tuesday July 20, 2021 @06:16AM
(#27891920)
Is it possible that P=NP is true but unprovable? And If that is the case, how do we prove it is unprovable?
[ Parent
| on HN ]
Re:A proof P = NP was accidentally published in TOCT
by natarajanda on Tuesday July 20, 2021 @07:44AM
(#27892547)
Godel's incompleteness theorem shows that it's possible for any axiomatic system (like mathematics) to have statements that are true but unproveable.
Re:A proof P = NP was accidentally published in TOCT
by kbelder on Tuesday July 20, 2021 @12:06PM
(#27895517)
But does it give a way of distinguishing which statements those are from other statements that are just not proven yet?
Re:A proof P = NP was accidentally published in TOCT
by mgsouth on Tuesday July 20, 2021 @03:06PM
(#27897847)
If you're asking "is this statement true but unprovable", then no, that would itself be a proof. It is possible to show that, within a particular set of mathematical rules, some statements are "either true or false, but we'll never be able to prove which." An example is the parallel postulate ("parallel lines neither converge nor diverge at infinity") [0]. This is impossible to either prove or disprove in Euclidian geometry, and has to be taken as a given truth.
Interestingly, showing a statement is unprovable implies that you can postulate either way (true or false) and still have a self-consistent mathematical structure. (If you assumed one way, and ran into an inconsistency, then that would be a proof the assumption is false and the opposite choice is true.) So if you assume the parallel postulate is true you get Euclidean geometry. If you assume false you get a non-Euclidean geometry such as Elliptic, Spherical, or Hyperbolic (depending on what additional postulates you choose).