## Saturday, November 17, 2012

### NP-dopey

I have to make an up-front disclaimer: I have a hard time stifling yawns when discussions of which problems are in NP, NP-complete, NP-hard or NP-anything come up. In fact, I have a tempered enthusiasm for computational complexity in general. The mathematics is perfectly solid, it's of theoretical interest to some people, but I find it hard to connect much of it to the practice of mathematical optimization.

A couple of things prompt this post. First, Jean Francois Puget wrote a very nice blog post about what it means for a problem to be in class NP versus class P (and what the distinction is between an optimization problem and decision problem, as it relates to complexity classification). More importantly, from my perspective, he tied the discussion to customer concerns ("Why does it take so long to solve my problem?" "Can I solve larger instances in reasonable time?"). Part of what I'm going to say here was originally contained in a comment I posted to his blog, but apparently commenting on that blog is NP-difficult; my comment shows up blank. So I'll express myself here, where I control what actually gets approved.

The second trigger was an incident at the recent INFORMS 2012 conference. During one of the coffee breaks, I had a discussion with a few colleagues about publishing optimization papers, during which at least a couple of us agreed that authors have an unfortunate tendency to say "Our problem is NP-something, so we have to use a heuristic [and here's the wonderful heuristic we concocted]." Well, the Traveling Salesman Problem is NP-hard. Heck, I think it was voted the poster boy for NP-hard problems. Nonetheless, give me a network with three nodes, and I will give you an exact solution to it. Catch me after a cup of coffee and before too many beers, and I can even do a five node problem without resorting to a heuristic. Sure enough, not long after the coffee break I was in a session where a presenter said that his problem was NP-hard, and therefore he and his coauthor were forced to use a heuristic. (The presenter was a student, so it's not too late to redeem his soul.)

The following are my personal opinions and, based on conversations I've had, not widely endorsed within the academic community:
1. Small instances of NP-hard problems can be solved exactly. Large instances are intractable. The same is true for polynomial problems (class P). The definition of "small" is "I can solve this easily". The definition of "large" is "this bugger takes too long to solve".
2. There was excitement in the academic community when it was discovered that linear programs (or at least those satisfying some conditions I never bothered to memorize) can be solved in polynomial time. As George Dantzig pointed out (and if anyone has the reference for this, please post it in a comment!), a polynomial can be a big number. If I tell you that a particular problem class has an algorithm that is polynomial with complexity $O(n^{2593})$, where $n$ is, say, the number of nodes in a network, does that make it sound easy to you? It sure doesn't to me.
3. Complexity results are asymptotic. To me, saying that problem A is in class P and problem B is in class NP means that as instances of the two problem grow larger and larger, I'll probably hit the barrier for what I can solve (with a contemporary computing platform, in acceptable time) sooner with problem B than with problem A. The thing is, I don't usually have problems where the instances grow and grow without bound. I have small instances that I use for testing and debugging, and I have the actual instances that need to be solved. If I can solve the instances I need to solve, I really don't care if the algorithm is polynomial time or not.
4. Implicit in my previous statements were some things that I think get lost sometimes when people are throwing NP-ness around. A problem class belongs to P or NP. An individual instance of that problem does not. Also, computational complexity needs to be viewed at the algorithm level. Problems in class NP are those for which nobody knows a polynomial-time algorithm. Problems in class P are those for which we do know polynomial-time algorithms. That doesn't mean you're necessarily using one. The simplex algorithm has nonpolynomial (worst case) complexity, but it is applied to linear programs -- which, as mentioned above, are class P -- quite commonly.
5. Computational complexity of an algorithm is a worst-case, asymptotic bound. I've already taken exception with the asymptotic part, since I don't typically worry about how computation time changes as my problems morph from huge to disgustingly huge. As far as the worst-case aspect, I don't typically expect to be solving the worst case. (Some days it seems like I am, but I'm probably just being grumpy.) I'd be more interested in knowing what complexity is on "average" problems, but even that might be deceptive - there might be something specific to my versions of the problem that would favor an algorithm that doesn't have the best "average" run times.
6. In complexity measurement, there are constants that typically get overlooked. Suppose we have a class of problems where we can represent the size of an instance by a single dimension $n$. Suppose further that we have two algorithms, one (A) with complexity $O(n^3)$ and the other (B) with complexity $O(n)$. It's pretty clear that want to use the linear time algorithm (B) rather than cubic time algorithm (A), correct? Well, what the complexity stuff means is that (worst case) the time/work for A is bounded by $M_A n^3$ while the time/work for B is bounded by $M_B n$, where $M_A$ and $M_B$ are constants (that we typically do not know). Regardless of the values of those constants, $\lim_{n\rightarrow \infty} \frac{M_B n}{M_A n^3}=0,$so for large enough $n$, B is the winner. If $M_A \ll M_B$, though, then for small $n$, A is the faster algorithm. This isn't just a hypothetical. Take sorting a list. Tree sort ($O(n\log(n))$) is asymptotically faster than bubble sort ($O(n^2)$), but tree sorts involve a bunch of overhead, so bubble sorts really are faster on short lists. If you are going to sort a large number of short lists, and you implement tree sort (because, hey, it's got better complexity), you'll pay for it.
7. The question of whether P = NP remains undecided, as far as I know. (There have been a few allegations of solutions in the last few years, but I don't think any have survived close scrutiny.) Like pretty much everyone, I believe they're not equal ... but if it turns out that P really does equal NP, won't all the people wringing their hands over this or that being NP-hard feel silly?
8. For authors of academic papers, it's fine to include a statement (and, if it's not obvious, a proof) that your problem (class) is NP-whatever. That's another tidbit added to the body of human knowledge. Just don't think it's license to launch into building some funky new heuristic without first testing standard or obvious solution approaches (assuming such approaches exist).
So, am I out to thoroughly diss computational complexity? No. First, it gives us an indication of whether a problem class is likely to be difficult to solve. I don't know a better way to classify problems into scary-looking versus not scary-looking. I just wish people would not read more into the classification than it warrants.

Second, implementing algorithms usually involves more algorithms. Solving a MIP by branch and bound? How are you going to solve the node problems (meaning what algorithm will you use)? Computing shortest paths through a network as a step in some larger algorithm? Will you use Dijkstra, Floyd-Warshall or something else? How will you sort lists of things? What data structures (which contain algorithms for insertion and retrieval) will you use? When I'm coding an algorithm, I don't have time to test all possible combinations of all possible component algorithms; so I frequently grab the option that I think has best complexity because, frankly, I don't have anything better to go on.

So, bottom line, many instances of problems in class NP can be solved, and large enough instances of class P problems cannot be solved. To paraphrase a former boss (discussing hard work), I'm not afraid of NP-hard problems. I can lie down right next to them and sleep peacefully.

#### Other voices (in no particular order):

1. Great post! I can't agree more. I'm glad your comment didn't make it to my blog as it results in this nice post.

I would be more interested in complexity theory if it was providing more results about average case complexity, as it would relate better to practice.

1. I agree, but "average" complexity requires a probability distribution on instances of a given size, and good luck finding that. Also, every silver lining comes wrapped in a cloud: a customer with instances of above (below) average complexity might be overly optimistic (pessimistic) about solution times. Still, unless you live under a serious curse, average is probably more useful than worst case.

2. I fully agree that just because a problem class is NP-complete, one shouldn't dismiss the possibility of devising or applying an optimal algorithm that works on problem instances of practical interest. Also I suspect that most people know in advance what kind of algorithm they like to study, and only later look for reasons to justify their choice. If you like to work on local-search heuristics that do not have an optimality guarantee, it's hard to justify applying your work to problems in P, so it is reasonable that you take care to observe that your problems are NP-hard; still, you shouldn't claim that NP-hardness made you turn to heuristics.

What I don't agree so much with is: "If I can solve the instances I need to solve, I really don't care if the algorithm is polynomial time or not." The trouble is that even if you know that you have been able to solve the instances that you needed to solve today, you have no actual evidence that you will be able to solve the instances that you need to solve tomorrow, or next week, or next year. Experience suggests that if you have a polynomial algorithm, you can be a lot more confident that a modest increase in problem size (or change in other problem characteristics) will lead to a manageable increase in computational effort. Exponential algorithms are observed to be much less reliable in this respect. There is some theory to explain this difference, but it can be observed empirically, as newcomers to mixed-integer programming inevitably learn.

This is only an argument about polynomial vs. exponential algorithms, not about NP-hardness. Should it turn out that P = NP and that efficient polynomial algorithms are available for all of the problem classes commonly of interest, then we'll have one less thing to worry about. But meanwhile there are instances to be solved ...

1. Bob,

I concede your point about today v. tomorrow. My perspective is probably colored by the fact that a number of the MIP applications I've dealt with (particularly recently) do not have the potential (or at least the likelihood) to grow significantly in size. That contrasts with many industrial users, who could be looking at nontrivial growth of model instances.

There's one glaring exception in my own experience, which is MIP models for discriminant/classification analysis. Problem complexity is there is governed partly by the number of observable attributes but mainly by sample size, and in the era of Big Data sample sizes are pretty much guaranteed to be somewhere between large and "holy cow!". That's one place where I would be very interested in finding a polynomial time algorithm (with low polynomial degree), although I doubt I'll ever see one.

3. I don't find that complexity theorists are misguided on the "practical" applications of complexity classes. In fact, the points you raise (especially P possibly having a really large exponent, which is a very tired objection) would most certainly force them into stifling yawns! :)

Complexity classes persist because they have a surprising theoretical value. Despite their apparent crudeness, they seem to still yield insight after decades of exploration. Better apparatus may come along eventually, but we have to start somewhere. The fact that the P/NP question remains unresolved after so much effort has been expended suggests that the solution will certainly demand great leaps in our understanding of the nature of computation.

I suppose what I'm objecting to is that you seem to be presenting your arguments as a contrarian opinion, when a complexity theorist would be the first to agree that they are not particularly interested in solving particular problem instances of "practical concern." On the other hand, you always reserve the right to be disinterested in the games others' play!

1. Nathan,

I'll confess that I have no real sense of precisely what interests complexity theorists. The "large exponent" argument won't stir them if they are focused on asymptotic complexity. Do you know to what extent they worry about computation time/size for "small" and "medium" problem sizes?

I didn't mean this post as a condemnation of complexity theory. It's the use of complexity results by the rabble, as a crude cudgel, that sends me into slumber land. (See Ryan's comment following yours.)

Your last sentence is spot on, and I'll add that while disinterest is fine, we need to be careful not to let it morph into disdain. When I was a student, number theory seemed to be one of those math-for-math's-sake areas. Nobody knew then that it would turn into the lynch pin for a gazillion dollar a year cryptography business sector courtesy of the not-yet-conceived Internet.

2. By the way, just to be clear, I don't think complexity theorists are misguided. I think it's a segment of the people charged with actually solving the problems that are misguided about what complexity actually means. Sorry if I was not clear about that.

4. This is a wonderful post!

One of my favorite anecdotes is from the INFORMS 2008 conference. I overheard a few senior OR people talking amongst themselves, when one declared, "NP-Hard is a term we use to scare graduate students."

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.