Maths et Délires
Des maths et des délires
 

Maths et Délires Index du Forum

 FAQFAQ   RechercherRechercher   Liste des MembresListe des Membres   Groupes d'utilisateursGroupes d'utilisateurs   S'enregistrerS'enregistrer 
 ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Est-ce que P = NP ?

 
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Délires et rires
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Overlord
Être mi-geek mi-globzoule


Inscrit le: 23 Juin 2005
Messages: 2446
Localisation: Belgique, Louvain-La-Neuve, Bâtiment des Fous.

MessagePosté le: 20 Oct 2006, 17:44    Sujet du message: Est-ce que P = NP ? Répondre en citant

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...
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger MSN Messenger
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Délires et rires Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com