Journal d'un Terrien
Web log de Serge Boisse
On line depuis 1992 !
Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/p_np.php
La conjecture P-NP
C'est l'une des plus célèbres conjectures mathématiques. Si vous la démontrez, vous gagnerez un million de dollars... Et pourtant son Enoncé est tout simple : "P est différent de NP"
Qu'est ce que ça veut dire ?
P est l'ensemble des familles de problèmes dont la solution peut être trouvée en un temps polynomial en fonction de la taille du problème par une machine de Turing (ou un ordinateur) déterministe
P est l'ensemble des familles de problèmes dont la solution peut être trouvée en un temps polynomial en fonction de la taille du problème par une machine de Turing (ou un ordinateur) non déterministe.
Ainsi NP ne signifie pas "non polynomial" mais "non déterministe et polynomial"
Pour comprendre ces définitions, il faut préciser ce que l'on entend par "famille de problème", par "déterministe" et "non déterministe", et par "temps polynomial"
Page en chantier
Désolé ! Sois patient...
< Retour à la page précédente
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.