Comments (8)
  • Add a Comment
  • Edit
  • More Actions v
  • Quarantine this Entry

1 msoos commented Permalink

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 JeanFrancoisPuget commented Permalink

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 PaulRubin commented Permalink

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 MGwynne commented Permalink

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 JeanFrancoisPuget commented Permalink

@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 PaulRubin commented Permalink

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 JeanFrancoisPuget commented Permalink

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).
 
I'll read your blog entry then (I can't wait!)
 

8 JeanFrancoisPuget commented Permalink

To be crystal clear on complexity, we should take into account the number of bits used to represent the numbers involved in the statement of a MIP or LP. The size of a problem is the actual number of bits used to represent it. For instance we could use the memory consumption as a size measure. However, given we work with fixed size numbers (machine integers and machine floating points, usually 64 bits per number), then the size is proportional to the number of numbers. It is why I used the latter s problem size in this post.