# 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$$.

Parents:

• P vs NP

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