Minimum degree of polynomial time NP complete problem algorithm

[Sandor]

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?

 

[fresh_42]

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?

It is generally harder to prove lower bounds, as one has to prove that something is impossible, rather than showing a smart algorithm. However, polynomial lower bounds are trivial. Every input character is needed in at least one calculation step, or otherwise is not necessary. This means we have at least $O(n)$ calculations.

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?

Depends on the problem. We have a trivial lower bound $O(n)$ and usually an exponential upper bound for NP problems, also trivial, as we simply can check all (exponentially many) possible answers.