[Math] How slow are direct solutions of NP-complete problems on computers

algorithmscomputer sciencenp

Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. Are there any? Are there any NP-complete problems with not very bad performance?

Best Answer

This 2003 paper shows there has been quite a bit of work. The focus is on "fast" exponential-time solutions to NP-hard problems, including the TSP, SAT, knapsack problems, graph coloring, to mention a few:

Woeginger, Gerhard J. "Exact algorithms for NP-hard problems: A survey." Combinatorial Optimization—Eureka, You Shrink!. Springer Berlin Heidelberg, 2003. 185-207. PDF download

For example, there is an exact algorithm for the Euclidean TSP in the plane (ETSP) with time complexity $O(2^{\sqrt{n} \log n})$. But as is well-known, S. Arora and J.S.B. Mitchell found PTAS's to solve ETSP.

This paper has been cited over 500 times since, showing there has been significant subsequent work.

Related Question