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.

$\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
    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$ Nov 14, 2015 at 16:03

2 Answers 2

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.

$\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$ 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.

$\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
    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
    Jul 24, 2010 at 21:40
  • $\begingroup$ Thanks. That result sounds interesting ... I'm going to have to look at it. $\endgroup$
    – Peter Shor
    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
    Jul 25, 2010 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.