Être mi-geek mi-globzoule
Inscrit le: 23 Juin 2005
Localisation: Belgique, Louvain-La-Neuve, Bâtiment des Fous.
|Posté le: 20 Oct 2006, 17:44 Sujet du message: Est-ce que P = NP ?
|Dans mon livre d'optimisation combinatoire, il y a écrit: |
A first important remark concerns the class NP. Typically, problems in this class have a very large set of feasible solutions, and these problems can in theory be solved by enumerating the feasible solutions. This is impractical for instances of any reasonable size.
A pessimist might say that as most problems appear to be hard (their decision version lies in NPC), we have no hope of solving instances of large size, because in the worst case we cannot hope to do better than enumeration, and so we should give up.
A mathematician (optimist) might set out to become famous by proving that P = NP.
A mathematician (pessimist) might set out to become famous by proving that P != NP.
A mathematician (thoughtful) might decide to ask a different question : can I find an algorithm that is guaranteed to find a solution "close to optimal" in polynomial time in all cases ?
A probabilist (thoughtful) might also ask a different question : can I find an algorithm that runs in polynomial time with high probability and that is guaranteed to find an optimal or "close to optimal" solution with high probability ?
An engineer would start looking for a heuristic algorithm that produces practically usable solutions.
Your boss might say : I don't care a damn about integer programming theory. You just worry about our scheduling problem. Give me a feasible production schedule for tomorrow in which William Brown and Daughters' order is out of the door by 4 PM.
A struggling professor might say : Great. Previously I was trying to develop one algorithm to solve all integer programs, and publishing one paper every two years explaining why I was not succeeding. Now I know that I might as well study each NP problem individually. As there are thousands of them, I should be able to write twenty papers a year.
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Il y a 11 catégories de gens sur Terre :
- Ceux qui vont sourire à cette blague parce qu'ils connaissent le binaire
- Ceux qui la connaissent et qui connaissent le binaire
- Ceux qui ne comprennent pas
Mais 10 d'entre eux ont VRAIMENT besoin de lâcher leur ordi...