2
$\begingroup$

Let's just say that some person discovered that $P = NP$ implies $P \neq NP$ and $P \neq NP$ implies $P = NP$, and we don't know what is causing this contradiction, And this was a valid proof that was accepted. What would the consequences of this be? This would probably be the least likely outcome of the P vs NP question. But one I don't see talked about.

$\endgroup$
2
  • $\begingroup$ It's not talked much about because it's the same as saying that $1 = 2$. A more realistic scenario is that neither $P=NP$ nor $P \neq NP$ can be proved in ZFC. That's called P vs NP being independent of our current axiomatic system. $\endgroup$
    – Pål GD
    Jan 9 at 16:07
  • $\begingroup$ @PålGD we can't rule out that we discover a contradiction in ZFC or even Peano Arithmetic(Though there is some proof that its consistent relative to another set of axioms, but that set has not been proven consistent yet.). Or it could be something as simple as we made a mistake in some other random computer science axiom or some theorem's proof had a subtle but deep error no one has figured out yet. $\endgroup$ Jan 9 at 20:31
1
$\begingroup$

If P=NP implies P≠NP, then P≠NP (unconditionally).

Similarly, if P≠NP implies P=NP, then P=NP.

If both are true, then both P≠NP and P=NP, and so the axioms of mathematics are inconsistent. Most (but not all) mathematicians consider this quite unlikely.

$\endgroup$
0
$\begingroup$

If you have a proof that $(P=NP)\Leftrightarrow (P\not= NP) $ then $P=NP$ is proveable is equivalent to $P\not= NP$ is provable. This would mean that neither $P=NP$ nor $P\not= NP$ is provable.

But if there would be a proof, that $P=NP$ is not provable then it would be proven that one cannot find an efficient algorithm for SAT or any other $NP$-complete problem. This would mean that $P \not= NP$. So, if $P$ versus $NP$ is independent from math then this would not be provable, too.

$\endgroup$
0

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.