LESSWRONG
LW

Wikitags
Main
1
Arguments against P=NP
4

P vs NP: Arguments against P=NP

Edited by Jaime Sevilla Molina, et al. last updated 5th Aug 2025

Natural proofs

If P≠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≠NP then proving P≠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.

If P=NP, the polynomial hierarchy collapses down to its lowest level, P. That is, every level L would have a polynomial reduction to level L-1, and the overall complexity would be a composition of polynomials (not exponential).

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≠NP.

Exponential time hypothesis

Trial and errors might be required, recursively. An exponential search tree might be required to solve hard instances. Or something else with equivalent complexity.

Parents:
P vs NP
4
4
Discussion0
Discussion0