- #1

- 10

- 0

## Main Question or Discussion Point

So no one is quite sure that P != NP, although they tend to favor that relation. But I was curious, has anyone proved a minimum degree order to any algorithm that solves NP complete problems in polynomial time? In other words, they don't know if it can be done in polynomial time, but do they know that it cannot be done in, say, quadratic time, and requires at least cubic time, or in cubic time and requires at least quartic time, or maybe they know that it is at least of order n^6? Maybe something kookier like n^3*(ln(n))^3?