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:

Natural proofs

If 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 then proving is hard.

The opposite proposition for is also expected to be true. That is, it would make sense that if 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 [ -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 , then evolution could have made use of this advantage to sped up its search process, or create more efficient minds to solve -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 ].