The domains of interest to me are: 1. Robotics 2. Search 3. NLP 4. Image feature extraction 5. Network optimization 6. Network security

  • 3
    $\begingroup$ The very point of NP-completeness is that many problems of real-world interest in various fields are NP-complete. Have you checked Garey and Johnson? $\endgroup$ Nov 21 '10 at 23:20
  • 4
    $\begingroup$ You can also look at the Wikipedia article, here: en.wikipedia.org/wiki/List_of_NP-complete_problems . If you mentioned why you were asking it could help people give you better answers, also. $\endgroup$ Nov 21 '10 at 23:47
  • 2
    $\begingroup$ this is terribly broad, and not well motivated. voting to close. $\endgroup$ Nov 22 '10 at 10:04
  • 7
    $\begingroup$ I think it's a reasonable question. Before Wikipedia, the compendium of NP optimization problems (csc.kth.se/~viggo/wwwcompendium) was very helpful, e.g., to find problems to prove are hard to approximate, or to get examples for a survey talk. It would have been good to have a compendium for more applied problems. $\endgroup$ Nov 22 '10 at 14:04
  • 4
    $\begingroup$ It would be nice to collect explanations of the parts of some real-world problems that are NP-hard. Bridges between the Garey & Johnson style lists, and problems closer to actual applications, could be broadly useful and are not immediately obvious to many people working in applied fields. However, this question seems far too broad, covering at least several dozen major questions! $\endgroup$ Nov 22 '10 at 15:51