P vs NP: Arguments against P=NP

Nat­u­ral proofs

If \(P \neq NP,\) then there are re­sults show­ing that lower bounds in com­plex­ity are in­her­ently harder to prove in a tech­ni­cal yet nat­u­ral sense. In other words, if \(P \neq NP\) then prov­ing \(P \neq NP\) is hard.

The op­po­site propo­si­tion for \(P=NP\) is also ex­pected to be true. That is, it would make sense that if \(P=NP,\) then it should be eas­ier to prove, since we could build far more effi­cient the­o­rem provers.

Em­piri­cal argument

We have been try­ing to get a fast al­gorithm for \(NP\)-com­plete prob­lems since the 70s, with­out suc­cess. And take into ac­count that “we” does not only com­prise a minor group of the­o­ret­i­cal com­puter sci­en­tists, but a whole in­dus­try try­ing to get faster al­gorithms for com­mer­cial pur­poses.

One could also ar­gue more weakly that if \(P=NP\), then evolu­tion could have made use of this ad­van­tage to sped up its search pro­cess, or cre­ate more effi­cient minds to solve \(NP\)-com­plete prob­lems at thought­speed.

The ar­ith­meti­cal hi­er­ar­chy argument

Some au­thors have drawn an anal­ogy be­tween the polyno­mial hi­er­ar­chy and the ar­ith­meti­cal hi­er­ar­chy.

There are re­sults show­ing that the ar­ith­meti­cal hi­er­ar­chy is strict, and if the anal­ogy holds then we would have that the polyno­mial hi­er­ar­chy is strict as well, which au­to­mat­i­cally im­plies \(P \neq NP\).


  • P vs NP

    Is cre­ativity purely me­chan­i­cal?