Journal d'un Terrien

Web log de Serge Boisse

On line depuis 1992 !

Publicité

Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/p_np.php

p_np
Metadata
Serge Boisse
Le 27/03/2023 à 11:03
web/MOC
oui
oui

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 ?

Définition : P

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

Définition : NP

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

Publicité
Commentaires

Commentaires (0) :

Page :



Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
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.
< Retour en haut de la page