Natural proofs

If \(P \neq NP,\) then there are results showing that lower bounds in complexity are inherently harder to prove in a technical yet natural sense. In other words, if \(P \neq NP\) then proving \(P \neq NP\) is hard.

The opposite proposition for \(P=NP\) is also expected to be true. That is, it would make sense that if \(P=NP,\) then it should be easier to prove, since we could build far more efficient theorem provers.

Empirical argument

We have been trying to get a fast algorithm for \(NP\)-complete problems since the 70s, without success. And take into account that “we” does not only comprise a minor group of theoretical computer scientists, but a whole industry trying to get faster algorithms for commercial purposes.

One could also argue more weakly that if \(P=NP\), then evolution could have made use of this advantage to sped up its search process, or create more efficient minds to solve \(NP\)-complete problems at thoughtspeed.

The arithmetical hierarchy argument

Some authors have drawn an analogy between the polynomial hierarchy and the arithmetical hierarchy.

There are results showing that the arithmetical hierarchy is strict, and if the analogy holds then we would have that the polynomial hierarchy is strict as well, which automatically implies \(P \neq NP\).