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

CC BY-SA 2.5
2010-11-21T23:20:58.657Z
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](http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness)?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-22T10:04:10.047Z
this is terribly broad, and not well motivated. voting to close.
Suresh Venkat
CC BY-SA 2.5
2010-11-22T14:04:57.063Z
I think it's a reasonable question. Before Wikipedia, the compendium of NP optimization problems (http://www.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.
Dana Moshkovitz
CC BY-SA 2.5
2010-11-22T15:51:37.843Z
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!
András Salamon
CC BY-SA 2.5
2010-11-24T23:48:34.687Z
Re: Philip - yes the page lists a number of NPC+ problems, but it does not show how they match to practical problems people are trying to solve.  It is the latter mapping I am asking for.
yters
CC BY-SA 2.5
2010-11-24T23:50:09.427Z
I ask this question because I think I have an approach for solving NPC+ problems better than current approaches, and need important practical problems to motivate interest in people with little or no computer science background.
yters
CC BY-SA 2.5
2010-11-25T09:45:24.037Z
My 0.02€: people who find it obvious that NP-complete(ness|problems) are of practical interest could help convince those who don't by adding such practical examples to that Wikipedia page.
Anthony Labarre
CC BY-SA 2.5
2010-11-25T17:32:13.423Z
Re: Anthony, good point.  Once I've established such a list I'll make sure I add it to the wikipedia page.
yters
<cc.complexity-theory><reference-request><np-hardness>
Is there a list of NPC or harder problems for specific real world problem domains?
yters
# Is there a list of NPC or harder problems for specific real world problem domains?

(Asked by: username_0 on 2010-11-21)

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

**Tags:** cc.complexity-theory, reference-request, np-hardness
> **Comments:**
> **username_1**: 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](http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness)?  
> **username_2**: this is terribly broad, and not well motivated. voting to close.  
> **username_3**: I think it's a reasonable question. Before Wikipedia, the compendium of NP optimization problems (http://www.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.  
> **username_4**: 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!  
> **username_0**: Re: Philip - yes the page lists a number of NPC+ problems, but it does not show how they match to practical problems people are trying to solve.  It is the latter mapping I am asking for.  
> **username_0**: I ask this question because I think I have an approach for solving NPC+ problems better than current approaches, and need important practical problems to motivate interest in people with little or no computer science background.  
> **username_5**: My 0.02€: people who find it obvious that NP-complete(ness|problems) are of practical interest could help convince those who don't by adding such practical examples to that Wikipedia page.  
> **username_0**: Re: Anthony, good point.  Once I've established such a list I'll make sure I add it to the wikipedia page.  

---

## 0 answers

