Minimum degree of polynomial time NP complete problem algorithm

  • Thread starter Sandor
  • Start date
  • #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?
 

Answers and Replies

  • #2
12,509
8,921
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.
 

Related Threads for: Minimum degree of polynomial time NP complete problem algorithm

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
11
Views
8K
  • Last Post
Replies
7
Views
4K
Replies
2
Views
2K
  • Last Post
Replies
2
Views
5K
Top