It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things like being able to find a proof for the Goldbach conjecture in polynomial time (if one exists), and so on.

However, are there some unintuitive consequences for the definitive statement that $P ≠ NP$?

A good example of what I mean is the axiom of choice. If you assume it, you can prove some pretty weird things, but if you assume its negation you can prove things that might be even weirder. The only way to avoid those things is not to assume anything at all. (Or assume one of its weaker variants.)

In this case, it's probably different because unless $P$ vs $NP$ is independent of ZFC, you can prove any statement if you assume the negation of the correct answer, so one can expect to get some strange consequences. But I hope my example got the point across.


Your Answer

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

Browse other questions tagged or ask your own question.