4 ms·

Is it possible that P=NP is true but unprovable? And If that is the case, how do we prove it is unprovable?

• natarajanda 5y ago
  Godel's incompleteness theorem shows that it's possible for any axiomatic system (like mathematics) to have statements that are true but unproveable.
  • kbelder 5y ago
    But does it give a way of distinguishing which statements those are from other statements that are just not proven yet?
    • kolinko 5y ago
      A way for distinguishing = a way to prove. Some things can be provably unprovable, but there will always be things that are unprovably unprovable. And unprovably unprovably unprovable :)
    • mgsouth 5y ago
      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). [0] https://en.wikipedia.org/wiki/Parallel_postulate https://en.wikipedia.org/wiki/Parallel_postulate