Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Peter Shor Jul 28 '10 at 0:24
add comment

2 Answers

up vote 18 down vote accepted

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.

share|improve this answer
    
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. –  Greg Kuperberg Nov 27 '09 at 21:10
add comment

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.

share|improve this answer
1  
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? –  Peter Shor Jul 24 '10 at 14:11
    
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. –  Charles Jul 24 '10 at 21:40
    
Thanks. That result sounds interesting ... I'm going to have to look at it. –  Peter Shor Jul 25 '10 at 15:26
    
It's cited in the Razborov-Rudich paper, I believe. I don't know if it's been published apart from that. –  Charles Jul 25 '10 at 18:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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