P contre NP

Le problème P versus NP est l'un des problèmes les plus importants et non résolus en informatique.

Complexité Computationnelle

La complexité computationnelle est une mesure de la difficulté (en termes de temps, mémoire ou d'un autre critère) d'exécuter un algorithme.

Exemple : Trier une liste. Avec l'algorithme Quicksort, la complexité est n2n^2n2 dans le pire des cas et nlog⁡(n)n \log(n)nlog(n) en moyenne, où nnn est la taille du tableau d'entrée.

Exemple : Trouver une valeur dans une liste non ordonnée.

Moyenne : (N+1)/2 comparaisons

Pire des cas : N

L'algorithme de recherche linéaire est un algorithme O(n).

Qu'est-ce que P vs NP ?

La classe P est composée de problèmes dont les solutions peuvent être TROUVÉES en temps polynomial.
La classe NP est composée de problèmes dont les solutions peuvent être VÉRIFIÉES en temps polynomial.

En d'autres termes, le temps polynomial peut être O(N²), O(N⁷), ou toute complexité polynomiale. L'idée derrière cette classification est que ces problèmes sont considérés comme "faciles" dans le sens où ils peuvent être résolus avec des capacités de calcul actuelles.

Quelle est la différence entre trouver une solution et vérifier une solution ?

Exemple :

Pour TROUVER UNE SOLUTION, nous devrions vérifier si 4819 est divisible par 2, 3, 5, 7, 11, 13, 17—c'est-à-dire vérifier quels nombres premiers le divisent.

Cependant, le problème inverse est beaucoup plus simple :

Avec une calculatrice de poche basique, nous pouvons VÉRIFIER que 79 × 61 = 4819.

Toute l'encryption moderne RSA est basée sur cette asymétrie !

Un problème peut être exponentiellement difficile à résoudre, avec une complexité O(2^N) ou O(N!), mais il peut néanmoins être facile à vérifier—ce qui signifie qu'il appartient à la classe NP.

Une machine déterministe fait référence à une machine de Turing, un modèle abstrait de calcul. Une machine de Turing non-déterministe, en revanche, se comporte comme une machine de Turing ordinaire mais peut explorer un nombre infini de branches en parallèle.

En résumé :

• Classe P : Temps polynomial – TROUVER la solution en temps polynomial (P).

• Classe NP : Temps polynomial non-déterministe – VÉRIFIER la solution en temps polynomial (P).

(NP ne signifie pas "Non-Polynomial" – ne faites pas cette erreur!)

NP-Complet et NP-Difficile

Clairement, P est contenu dans NP—car s'il est possible de trouver une solution, il est aussi possible de vérifier si une solution satisfait le problème.

Cependant, dans le Zoo de la Complexité, il existe quelques entités supplémentaires. Quelles sont-elles ?

NP-Complet et NP-Difficile

• NP-Complet – Ce sont les problèmes de décision les plus difficiles au sein de la classe NP.

Un problème est NP-Complet si chaque problème dans NP peut être converti en lui en temps polynomial.

Exemples : Problème du voyageur de commerce, Satisfaction (SAT), Couverture de sommet, etc.
Voir Les 21 problèmes NP-Complets de Karp pour plus d'exemples.

En d'autres termes, imaginez que nous avons un solveur efficace (algorithme en temps polynomial) pour le problème du voyageur de commerce. Puisque chaque problème NP peut être transformé en le problème du voyageur de commerce, le résoudre efficacement signifierait que tous les problèmes NP pourraient également être résolus efficacement. Si vous résolvez un problème NP-Complet, vous les résolvez tous.

• NP-Difficile – Ce sont des problèmes qui sont aussi difficiles que NP-Complet, mais ils n'ont pas nécessairement des solutions qui peuvent être vérifiées en temps polynomial.

Les problèmes d'optimisation qui surgissent dans la vie réelle, tels que l'optimisation des récoltes ou la planification forestière, impliquent souvent des variables linéaires et entières avec de nombreuses contraintes—ce sont typiquement NP-Difficiles.

P = NP ou non ?

La grande question est de savoir si P = NP ou non. Cela peut sembler simple, mais à ce jour, personne n'a pu prouver ou infirmer cette affirmation.

Il y a même un prix de 1 million de dollars pour quiconque résout la question. C'est l'un des sept Problèmes du Millénaire, promus par le Clay Mathematics Institute.

🔗 Problèmes du Millénaire – Clay Mathematics Institute

Le Clay Institute s'est inspiré des 23 problèmes proposés par le mathématicien David Hilbert en 1900, qui, d'une manière ou d'une autre, ont guidé le développement des mathématiques dans les décennies suivantes.

Concernant le Zoo de la Complexité, étant donné que résoudre la question principale (P vs NP) est difficile, les mathématiciens se concentrent sur la résolution de problèmes qui peuvent être abordés. Cela a conduit à la création de diverses autres définitions des types de complexité computationnelle.

L'Informatique Quantique le Résout-elle ?

Lorsque de nouveaux paradigmes informatiques, tels que l'informatique quantique, émergent, comprendre leur potentiel permet de définir des limites et des attentes.

Dans le cas de l'informatique quantique, on pense qu'elle est plus puissante que la classe P, mais incapable de résoudre tous les problèmes NP. Elle pourrait également être capable de résoudre des problèmes au-delà de la classe NP.

En réalité, juste parce qu'un problème est polynomial, cela ne signifie pas nécessairement qu'il est facile. Un problème avec une complexité O(N⁹⁹⁹⁹) serait encore extrêmement difficile à résoudre.

En revanche, les problèmes NP-complets avec des petites tailles d'entrée peuvent effectivement être résolus avec la puissance de calcul actuelle. En pratique, les solveurs modernes ont rendu au moins partiellement solubles des problèmes auparavant insolubles pour des applications du monde réel. Grâce aux avancées en matière de matériel et de logiciels, il est possible de gérer les problèmes NP-Difficiles, au moins une partie significative d'entre eux.

Eh bien, dans tous les cas, il y a un prix de 1 million de dollars pour quiconque est prêt à plonger profondément dans le sujet ! N'allez juste pas gagner et refuser le prix comme l'a fait Grigori Perelman (voir le lien ci-dessous) !

🔗 L'Homme qui méritait un prix de 1 million de dollars — Et l'a refusé