Problème du millenaire

[rickpat]

La nature des problèmes
Qu'est-ce qui distingue les problèmes P des NP ? Un problème P se décompose en un algorithme, une suite de calculs élémentaires. Par exemple, additionner 2 nombres à 4 chiffres requiert 12 étapes élémentaires. Evidemment, plus le nombre de chiffres augmente, plus le nombre d'étapes augmente. On parle d'augmentation à temps polynomial. Pour des données de taille N, il nécessite au plus N*C^k opérations élémentaires avec C et k fixés. Les ordinateurs peuvent mener à bien ces opérations.
Maintenant, prenons un exemple simple, celui du voyageur de commerce. Il doit couvrir 3 villes selon un trajet minimum. Pour cela il doit étudier chaque itinéraire possible puis définir le plus court. Facile, cela offre 6 chemins différents. Mais avec 10 villes, il y en a 3 628 800. Et avec 25, plus de 10 ^26 ! C'est énorme et à ce jour, personne ne connaît de méthode pratique pour ce type de problème.
On parle de problème NP, processus polynomial mais non déterministe. Seul le nombre élevé de possibilités pose problème. Un ordinateur capable de faire des choix pourrait vérifier qu'une solution donnée convient en un temps polynomial. C'est le cas de la factorisation d'un entier en produit de facteurs premiers. On ne sait pas s'il existe un algorithme polynomial qui réussisse cette opération. Autrement dit, on ne sait pas si ce problème est dans P. En revanche, étant donné des nombres a, b, c…, on peut facilement vérifier si ce problème est dans NP.
A-t-on P=NP ? Autrement dit, peut-on trouver en temps polynomial ce que l'on peut prouver en temps polynomial?
Précédente

[Ben314]

Salut,
Pas trés cohérent ni très clair ton truc...
- Déjà, un algo est dit "en temps polynomial", ça veut dire que le temps d'exécution est majoré par du C.N^k où N et la "taille de l'entrée" et C et k des constante (ce que tu écrit, ça a pas trop de sens vu que, ci C et k sont des constantes alors C^k est aussi une constante).
- Ensuite, des phrases du style "...existe un algorithme polynomial pour factoriser un nombre N", c'est dénué de sens vu que tu ne précise pas polynomial par rapport à quoi.
Le type qui connait le domaine sait que c'est "...polynomial par rapport au nombre de chiffres de N", mais, vu son contenu, je pense pas que ta prose s'adresse à des spécialistes. Par contre, le profane, vu que la phrase n'a pas de sens, il est fort probable qu'il la complète sous la forme "...polynomial par rapport a N" ce qui est absurde vu qu'il est évident qu'on peut trouver la décomposition de N en moins de N tests : déjà l'algo. le plus basique qui soit il essaye de diviser N par tout les entiers de 1 à racine(N) et a une complexité en racine(N)
- La fin concernant la définition de ce qu'est un problème NP, si on connait le domaine, on y retrouve (très vaguement) ces petits, mais ça m'étonnerais fort qu'un profane y comprenne quoi que ce soit. La dernière phrase par exemple "En revanche, étant donné des nombres a, b, c…, on peut facilement vérifier si ce problème est dans NP.", j'ai plus que de gros doutes concernant le fait que ça puisse éclairer qui que ce soit (qui est "ce problème" ? quel rapport avec les nombres a,b,c ?)
- Enfin, Oukélé ta question à toi sur le sujet ?
Si c'est "Est ce que P=NP ?" ta question, alors la réponse, c'est "on en sait rien à l'heure actuelle".