Comentarios (8)

1 ha hecho un comentario el

Nice post! I think theoretical departments at universities have been pushing this "NP=impossible" into the heads of students a bit too much, and so we get well-educated people thinking "this is known to be impossible" and laypeople thinking "these guys went mad thinking it's impossible". It would be good to not only teach the theory, but give large real-world examples where it is possible (e.g. scheduling), and small real-world examples where it's essentially impossible (e.g. crypto).

2 ha hecho un comentario el

Thank you. I agree.

One thing that often make MIP fast enough in practice is the use of the LP relaxation, which can be computed in polynomial time. It may even happen that the LP relaxation provides an integer solution right away.

3 ha hecho un comentario el

Thanks for the link, and for a well-wrritten post on a sometimes confusing (and, to me, often annoying) subject

At the last INFORMS meeting, during a coffee break, I had an entertaining conversation about the tendency of people to say "it's NP-<modifier>, so we need to use a heuristic!" Sure enough, in an afternoon session a presenter said just that. (The presenter was a student, so hopefully he's still trainable.) My new stock response to this is that the TSP is NP-hard. That said, give me three nodes and I'll find you your optimal circuit

Your point about the real goal -- estimating how long a larger problem instance will take -- is spot on. Unfortunately, complexity theory is not much help, since it deals in worst cases and not averages. With LPs, you can probably make an educated guess, but MILPs are such cussed beasts that the best response I can ever come up with is "could be LOT longer". It is also possible that the larger instance will be faster to solve ... which might cause the user to think that an even larger instance will be faster still.</modifier>

4 ha hecho un comentario el

I find it interesting how people are willing to try to figure out whether their program is correct (and hence likely terminates), or to search for proofs to various non-trivial propositions - yet in general these problems are undecidable. In comparison problems in NP are easy - we will at least *eventually* find a solution!

I always like to think of a problem being NP-complete purely as an expressiveness property - the problem is interesting enough that we can model other interesting things in it. Sure, there are (likely) some things we won't be able to solve in our lifetimes but who is to say that those are going to be things we want to solve...

5 ha hecho un comentario el

@MGwynne, good point. There is a whole zoo of problem classes more complex than NP indeed.

@Paul Rubin, your comment is blank, I doubt it is intended, unless you are speechless given how good my post is! ;-)

6 ha hecho un comentario el

Jean Francois: I think your employer has a spam filter specifically targeted to my ID. I started my previous comment with a compliment about your post (very nice job explaining NP-ness), but apparently that wasn't enough. The rest I think I'll put in a post on my own blog; I'm overdue for one, and I have an opinion about NP issues that might be too long-winded for a comment anyway.

7 ha hecho un comentario el

Paul,

thanks, other readers reported issues with posting comments on Nov 15, I am sorry for that.

Now things seem to be back to normal (or the anti Rubin filter has been deactivated).