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?
$\begingroup$
$\endgroup$
8
-
4$\begingroup$ Perhaps you might find a bit about this if you read about SAT solvers. (Disclaimer: This is not an area I am familiar with.) $\endgroup$– Martin SleziakSep 1, 2016 at 10:40
-
1$\begingroup$ This post on MathOverflow might also be of interest in connection with your question: Solving NP problems in (usually) Polynomial time? $\endgroup$– Martin SleziakSep 1, 2016 at 10:41
-
2$\begingroup$ Right. More often than not these days, you get much better performance by encoding a problem as a SAT instance and passing it to a SAT solver rather than trying to implement a direct algorithm from scratch. Industrial-strength SAT solvers use lots of tricks and optimizations to make them run amazingly fast on problems typically coming from practice. $\endgroup$– Emil JeřábekSep 1, 2016 at 11:40
-
$\begingroup$ What do you mean by "bad performance"? For example, this is an NP complete problem: given a graph, if the graph has fewer than $2^{2^{100}}$ nodes then return 1, else return 1 if and only if the graph has a Hamiltonian cycle. I can write a very fast algorithm for every instance of that problem which can actually be evaluated on a computer. More seriously: we expect that some algorithms have exponential growth in runtime, but very slow exponential growth, so that in practical cases the runtime is virtually constant. So finding a good meaning of bad performance may be difficult. $\endgroup$– Carl MummertSep 1, 2016 at 12:34
-
2$\begingroup$ I went to a lovely colloquium lecture not long back on the Travelling Salesman Problem. The speaker's starting point was that it's completely wrong to interpret "NP-complete" as "not worth trying to solve", and that there is a huge industry of developing effective algorithms for practical instances of TSP. The speaker was Bill Cook, who has written a popular book on exactly this subject, "In Pursuit of the Travelling Salesman" (press.princeton.edu/titles/9531.html). If the book's as good as the lecture was, it would certainly be worth reading. $\endgroup$– David LoefflerSep 2, 2016 at 8:55
|
Show 3 more comments
3 Answers
$\begingroup$
$\endgroup$
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.
answered Sep 1, 2016 at 11:48
$\begingroup$
$\endgroup$
For Boolean Satisfiability (SAT), there is Sat Competition: http://www.satcompetition.org/
State of the art SAT solvers often perform very efficiently, far faster than exponential. At the above link there should be results to see how large instances were solved.
Sucess story: Using SAT solver, important partial results about a conjecture of Erdos were found. The formula was quite big, for details see here: http://cgi.csc.liv.ac.uk/~konev/SAT14/
Sometimes heuristic algorithms perform very fast on graph problems.
For SAT, if you generate random SAT instance, very likely state of the art SAT solver will solve it very fast. (There was very similar question about this here).
$\begingroup$
$\endgroup$
In full generality, the closest vector problem (CVP) is NP-complete. The LLL algorithm gives an approximate solution in polynomial time. The LLL-BKZ variant gives better approximations as the block size increases (the "B" stands for "Block"). Eventually, when the blocksize equals the dimension, the algorithm solves CVP (in exponential time). There has certainly been lots of experimentation benchmarking run-time (which is more-or-less exponential in the blocksize) versus how good the output is. This has also been done with lattices that have some "smaller than expected" vectors hidden in them. (There are applications in cryptography.)
answered Sep 1, 2016 at 11:51