Best-case Running-time to solve an NP-Complete problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T11:35:46Z http://mathoverflow.net/feeds/question/6418 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6418/best-case-running-time-to-solve-an-np-complete-problem Best-case Running-time to solve an NP-Complete problem Claudiu 2009-11-22T01:39:49Z 2010-05-15T18:39:19Z <p>What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of <a href="http://en.wikipedia.org/wiki/Travelling%5Fsalesman%5Fproblem" rel="nofollow">travelling salesman</a> is \$O(n!)\$, but with dynamic programming it can be done in \$O(n^2 2^n)\$. Is there any "easier" NP-Complete problem that has a better running time?</p> <p>Note that I'm curious about exact solutions, not approximations.</p> http://mathoverflow.net/questions/6418/best-case-running-time-to-solve-an-np-complete-problem/6420#6420 Answer by David Eppstein for Best-case Running-time to solve an NP-Complete problem David Eppstein 2009-11-22T02:08:39Z 2009-11-22T02:43:02Z <p>If P is an NP-complete problem, then define P<sub>k</sub> = instances of P in which the instances have been blown up from size n to size n<sup>k</sup> by padding them with blanks. Then P<sub>k</sub> is also NP-complete, but if P takes time exp(p(n)) to solve where p is some polynomial then P<sub>k</sub> can be solved in time essentially exp(p(n<sup>1/k</sup>)) (there's a little more time required to check that the input really does have the right amount of padding but unless the running time is polynomial this is a negligable fraction of the total time). So there is no "easiest" problem: for every problem you name this construction gives another easier but still NP-complete problem.</p> <p>As for non-artificial problems: most hard graph problems like Hamiltonian circuit, that are hard when restricted to planar graphs, can be solved in time exponential in &radic;n or in (&radic;n)(log&nbsp;n) by dynamic programming using a recursive partition by graph separators.</p> http://mathoverflow.net/questions/6418/best-case-running-time-to-solve-an-np-complete-problem/24793#24793 Answer by Charles for Best-case Running-time to solve an NP-Complete problem Charles 2010-05-15T18:39:19Z 2010-05-15T18:39:19Z <p>If P = NP, then there is a polynomial-time algorithm for solving any given NP-Complete problem. Otherwise, it's known that there exist no general algorithms for any NP-Complete problem that are better than half-exponential: that is, f(x) where f(f(x)) is exponential.</p>