- #1

- 10

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Sandor
- Start date

- #1

- 10

- 0

- #2

- 16,436

- 15,485

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.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?

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.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?

Share: