4
$\begingroup$

I'm a novice to the topic of provability so bear with me...

During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an unprovable statement. My friend opposed that, if indeed it was unprovable, then this would imply that there cannot be a polynomial time algorithm for NP-hard problems (as the existence of such proves the statement), thus implying $NP \neq P$. This seems to be imply that the statement cannot be unprovable or am I missing something?

$\endgroup$
5
$\begingroup$

Statements that are independent are not true or false, their truth value just cannot be decided given the axioms. For example, consider natural numbers. It is true that a given number is a product of primes. It is unprovable that a given number is prime, nor that it is not prime – since it depends on the number. For each given number, it is either prime or not, but it depends.

The same goes for independent statements – the "number" is here replaced with the set-theoretic universe (or whatever universe you base your logic in). It could be that in some universes P equals NP, while in some universes the two are different. The "real world" is one of these particular universes, but as Gödel showed, it is impossible to completely describe the real world: there will always be independent statements. When faced with one, we could try to find other properties of the real world which help determine the statement. This approach hasn't fared so well on the canonical example, the continuum hypothesis.

Despite the foregoing, it is not considered likely that the P vs. NP question is one of these independent statements. That's a declaration of faith. Even though it seems hard to settle, most theoreticians believe that it is just a difficult question, similar to many other difficult questions in mathematics, some of which have been solved one way or another (for example, Fermat's last theorem), some of them haven't (for example, the Riemann hypothesis).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.