14
$\begingroup$

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman 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?

Note that I'm curious about exact solutions, not approximations.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ There are a lot of NP-complete problems which are linear-time (or $n \log n$ time) reducible to 3-SAT (and vice versa). If one of these can be solved in $2^{O(n^\alpha)}$ time for $\alpha < 1$, they all can be. Most computer scientists think this is unlikely. $\endgroup$
    – Peter Shor
    Commented Jul 28, 2010 at 0:24
  • $\begingroup$ If it is travelling salesman problem,that graph can be decomposed small known graph which computer have already calculated. $\endgroup$
    – Takahiro Waki
    Commented Nov 14, 2015 at 16:03

2 Answers 2

Reset to default
25
$\begingroup$

If P is an NP-complete problem, then define Pk = instances of P in which the instances have been blown up from size n to size nk by padding them with blanks. Then Pk is also NP-complete, but if P takes time exp(p(n)) to solve where p is some polynomial then Pk can be solved in time essentially exp(p(n1/k)) (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.

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 √n or in (√n)(log n) by dynamic programming using a recursive partition by graph separators.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Let me just add that the reparametrization phenomenon in the first paragraph is unavoidable even for "natural" problems. For example, the question itself asserts that travelling salesman is $O(n!)$ in the naive algorithm. However, if we simplify traveling salesman to the directed Hamiltonian path problem, then rigorously, as a function of the input length, the naive algorithm is actually $O(\sqrt{n}!)$ time. $\endgroup$
    – Greg Kuperberg
    Commented Nov 27, 2009 at 21:10
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Where is this result proved? It seems very surprising to me. Is what you're saying that the optimal algorithm for SAT might take $O(n^5)$ time, it might take $O(2^{\sqrt{n}})$ time, but it cannot possibly take $O(n^{\log \log n})$ time? Or am I misunderstanding your answer? $\endgroup$
    – Peter Shor
    Commented Jul 24, 2010 at 14:11
  • 1
    $\begingroup$ I was thinking of Wigderson's result that a proof that DISCRETE-LOG can be solved in $O(f(x))$ time can be transformed into a proof that it can be solved in $O(\exp(f^{-1}(x))$. But this applies only to natural proofs in the sense of Razborov-Rudich, so I was wrong my claim. $\endgroup$
    – Charles
    Commented Jul 24, 2010 at 21:40
  • $\begingroup$ Thanks. That result sounds interesting ... I'm going to have to look at it. $\endgroup$
    – Peter Shor
    Commented Jul 25, 2010 at 15:26
  • $\begingroup$ It's cited in the Razborov-Rudich paper, I believe. I don't know if it's been published apart from that. $\endgroup$
    – Charles
    Commented Jul 25, 2010 at 18:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .