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
Savez-vous quels sont les articles les plus vendus sur Amazon.fr ?
p_np
science > maths > p_np

La conjecture P-NP

Pasted image 20250412202114.png hélas, c'est pas si simple !

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". Nous y reviendrons.

La grande majorité des mathématiciens professionnels estiment que . Cela ne vous étonnera pas si je pense le contraire...

Page en chantier

Désolé ! Sois patient...

Publicité
Commentaires

Commentaires (1) :

Page : [1] 

Alain Valade
Le 28/06/2025 à 03h03
J`ai lu quelque part qu`un étudiant en Informatique disait que selon lui la différence entre les problèmes P et les NP n`était pas claire . J`y pige qe dal en Informatique MAIS si c`est le cas alors pour moi ça clarifie la situation puisque cela rend presque inévitable que P=NP !! . . . comme pour la couleur de peau pour les racistes qui font une différence entre un Blanc et un Noir alors que toutes les teintes entre les deux sont repoussées du revers de la main .


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