Algorithmic Analysis - Are there any algorithms having their best case complexity of the order of n^99?

Question

Are there any algorithms having their best case complexity of the order of n^99? Is this NP complete? If not, how do we analyse such algorithms?

Answer 1

One such problem is a k-clique problem.

Given a graph of size n, is there any clique with k vertices? (k is considered a constant).

An obvious brute-force algorithm checks all k-subsets of graph vertices and tests them for being a clique. Since there are (n^k) k-subsets, and each can be checked in (k²) time, the total complexity becomes (n^kk²) or just (n^k) (because k is a constant).

The asymptotically best known algorithm for this problem (totally impractical though) runs in (n^0.792k).

By varying k, one can deal in any desired complexity.

Answer 2

Are there any algorithms having their best case complexity of the order of n^99?

Consider the following algorithm:

• read the input, keeping track of its length n.
• emit an output of length n⁹⁹.

(Well, that's not a very precise description, but you get the idea. Just do 99 nested loops that all iterate over the input, and have the innermost loop print x or something.)

Is this NP complete?

This is equivalent to asking, "Does P = NP?". If you can find the answer, you'll be famous. :-)

Answer 3

An algorithm having complexity N^99 is, by definition, polynomial time, so is in P. If you can find one that is NP-complete, you will have proved that P=NP, so I think it is unlikely that you will find one that is NP-complete.

One of the reasons that P vs NP is so interesting is that in practice algorithms in P that we come across naturally tend to have powers much smaller than 99. However there are ways to construct very artificial algorithms of almost arbitrary complexity, so there are definitely algorithms of complexity N^99. (See e.g. https://en.wikipedia.org/wiki/Time_hierarchy_theorem or observe that the number of circuits of a particular size grows more slowly than the number of different boolean functions so there must be some functions that do not have circuits of a particular size)

FWIW Donald Knuth believes that P=NP, but with a hard to find algorithm whose exponent is very large. See e.g. question 17 in http://www.informit.com/articles/article.aspx?p=2213858. This is not a contradiction to there being more complex algorithms with larger exponents: these algorithms would be doing other things (in fact, they might be very artificial).

Answer 4

You have to be a bit careful with how you phrase this question. Only problems can be NP-complete, not algorithms, so even if I could devise an algorithm for a problem that was the most efficient possible and which ran in time Θ(n⁹⁹), the algorithm wouldn't be NP-complete.

For a problem to be NP-complete, it would have to be a decision problem, a problem that takes in some input and outputs either "yes" or "no." So you could ask the following question: are there any decision problems that cannot be solved in time less than Θ(n⁹⁹), and if so, is such a problem NP-complete?

There's a result called the time hierarchy theorem that says that for most well-behaved functions, there are decision problems that can be solved within that amount of time, but not much less than it. In particular, we can construct a decision problem that can be solved in time Θ(n⁹⁹) but which cannot be solved in time O(n⁹⁹ / log n), for example. To the best of my knowledge we don't know of any decision problems whose most efficient possible algorithm runs in time exactly Θ(n⁹⁹), though as you can see we can get pretty close!

So are these problems NP-complete? Well, we don't know! Any problem with this property would belong to class P. In the event that P = NP, then it would end up being NP-complete not because there's something special about n⁹⁹ but because every problem in P would be NP-complete.* On the other hand, if P ≠ NP, then this problem could not be NP-complete because no NP-complete problems would belong to P. Again, there's nothing special here about n⁹⁹ other than the fact that it's a polynomial.

* Technically, the two trivial problems ("given an input, is 0 = 0?" and "given an input, is 0 = 1?") would not be NP-complete if P = NP.