P vs NP: Arguments against P=NP
If \(P \neq NP,\) then there are results showing that lower bounds in complexity are inherently harder to prove in a . 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 .
We have been trying to get a fast algorithm forproblems 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 arithmetical hierarchy.and the
There are results showing that the, and if the analogy holds then we would have that the polynomial hierarchy is strict as well, .
- P vs NP
Is creativity purely mechanical?