# P vs NP: Arguments against P=NP

https://arbital.com/p/arguments_against_P_NP

by Jaime Sevilla Molina Jun 14 2016 updated Jul 8 2016

Why we believe P and NP are different

[summary:

• Proving $P \neq NP$ is harder if true than proving $P=NP$ if true.
• After 50 years we haven't found any efficient algorithm for $NP$-complete problems.
• The polynomial hierarchy is compared to the arithmetical hierarchy, and the analogy implies $P \neq NP$ ]

# Natural proofs

If $P \neq NP,$ then there are results showing that lower bounds in complexity are inherently harder to prove in a [natural_proof 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, [collapseofthepolynomialhierarchy which automatically implies $P \neq NP$].