Nous avons écrit sur des algorithmes efficaces pour résoudre des problèmes complexes, comme le chemin le plus court, le graphe d’Euler, l’arbre couvrant minimum, etc. Ce sont toutes des réussites de concepteurs d’algorithmes. Dans cet article, des histoires d’échecs de l’informatique sont discutées.
Tous les problèmes informatiques peuvent-ils être résolus par un ordinateur? Il y a des problèmes de calcul qui ne peuvent pas être résolus par des algorithmes même avec un temps illimité. Par exemple, Problème d’arrêt de Turing (Étant donné un programme et une entrée, si le programme s’arrêtera éventuellement lorsqu’il sera exécuté avec cette entrée, ou s’exécutera pour toujours). Alan Turing a prouvé que l’algorithme général pour résoudre le problème d’arrêt pour toutes les paires programme-entrée possibles ne peut pas exister. Un élément clé de la preuve est que la machine de Turing a été utilisée comme définition mathématique d’un ordinateur et d’un programme (Problème d’arrêt de la source).
Le statut des problèmes NP complets est une autre histoire d’échec, les problèmes NP complets sont des problèmes dont le statut est inconnu. Aucun algorithme de temps polynomial n’a encore été découvert pour un problème NP complet, et personne n’a encore été en mesure de prouver qu’aucun algorithme de temps polynomial n’existe pour aucun d’entre eux. La partie intéressante est que si l’un des problèmes NP complets peut être résolu en temps polynomial, alors tous peuvent être résolus.
Quels sont les problèmes NP, P, NP-complete et NP-Hard ?
P est un ensemble de problèmes qui peuvent être résolus par une machine de Turing déterministe en temps polynomial.
NP est un ensemble de problèmes de décision qui peuvent être résolus par une machine de Turing non déterministe en temps polynomial. P est un sous-ensemble de NP (tout problème pouvant être résolu par une machine déterministe en temps polynomial peut également être résolu par une machine non déterministe en temps polynomial).
De manière informelle, NP est un ensemble de problèmes de décision qui peuvent être résolus par un temps polynomial via un « Algorithme Chanceux”, un algorithme magique qui fait toujours une bonne supposition parmi l’ensemble de choix donné (Source Ref 1).
Les problèmes NP-complets sont les problèmes les plus difficiles de l’ensemble NP. Un problème de décision L est NP-complet si:
1) L est dans NP (Toute solution donnée pour des problèmes NP-complets peut être vérifiée rapidement, mais il n’y a pas de solution connue efficace).
2) Chaque problème dans NP est réductible à L en temps polynomial (La réduction est définie ci-dessous).
Un problème est NP-dur s’il suit la propriété 2 mentionnée ci-dessus, n’a pas besoin de suivre la propriété 1. Par conséquent, l’ensemble NP-complet est également un sous-ensemble de l’ensemble NP-dur.
Problèmes de décision par rapport à l’optimisation
NP-l’exhaustivité s’applique au domaine des problèmes de décision. Il a été mis en place de cette façon car il est plus facile de comparer la difficulté des problèmes de décision que celle des problèmes d’optimisation. En réalité, cependant, être capable de résoudre un problème de décision en temps polynomial nous permettra souvent de résoudre le problème d’optimisation correspondant en temps polynomial (en utilisant un nombre polynomial d’appels au problème de décision). Ainsi, discuter de la difficulté des problèmes de décision équivaut souvent à discuter de la difficulté des problèmes d’optimisation. (Source Réf. 2).
Par exemple, considérons le problème de couverture de sommet (Étant donné un graphique, découvrez l’ensemble de sommets de taille minimale qui couvre tous les arêtes). C’est un problème d’optimisation. Le problème de décision correspondant est, étant donné les graphes non orientés G et k, existe-t-il une couverture de sommet de taille k?
Qu’est-ce que la réduction ?
Soit L1 et L2 deux problèmes de décision. Supposons que l’algorithme A2 résout L2. Autrement dit, si y est une entrée pour L2, l’algorithme A2 répondra Oui ou Non selon que y appartient à L2 ou non.
L’idée est de trouver une transformation de L1 en L2 pour que l’algorithme A2 puisse faire partie d’un algorithme A1 pour résoudre L1.
La réduction de l’apprentissage en général est très importante. Par exemple, si nous avons des fonctions de bibliothèque pour résoudre certains problèmes et si nous pouvons réduire un nouveau problème à l’un des problèmes résolus, nous économisons beaucoup de temps. Prenons l’exemple d’un problème où nous devons trouver le chemin de produit minimum dans un graphe dirigé donné où le produit du chemin est la multiplication des poids des arêtes le long du chemin. Si nous avons du code pour l’algorithme de Dijkstra pour trouver le chemin le plus court, nous pouvons prendre le journal de tous les poids et utiliser l’algorithme de Dijkstra pour trouver le chemin de produit minimum plutôt que d’écrire un nouveau code pour ce nouveau problème.
Comment prouver qu’un problème donné est NP complet ?
D’après la définition de NP-complet, il semble impossible de prouver qu’un problème L est NP-complet. Par définition, cela nous oblige à montrer que chaque problème dans NP est en temps polynomial réductible à L. Heureusement, il existe un autre moyen de le prouver. L’idée est de prendre un problème NP-complet connu et de le réduire à L. Si une réduction en temps polynomial est possible, nous pouvons prouver que L est NP-Complet par transitivité de réduction (Si un problème NP-Complet est réductible à L en temps polynomial, alors tous les problèmes sont réductibles à L en temps polynomial).
Quel a été le premier problème prouvé comme NP-complet?
Il doit y avoir un premier problème NP-Complet prouvé par définition de problèmes NP-Complets. SAT (problème de satisfiabilité booléenne) est le premier problème NP-complet prouvé par Cook (voir le livre CLRS pour la preuve).
Il est toujours utile de connaître la NP-complétude, même pour les ingénieurs. Supposons qu’on vous demande d’écrire un algorithme efficace pour résoudre un problème extrêmement important pour votre entreprise. Après beaucoup de réflexion, vous ne pouvez trouver qu’une approche temporelle exponentielle, ce qui n’est pas pratique. Si vous ne connaissez pas la NP-complétude, vous pouvez seulement dire que je ne pourrais pas venir avec un algorithme efficace. Si vous connaissez la NP-complétude et prouvez que le problème est NP-complet, vous pouvez dire avec fierté que la solution en temps polynomial est peu susceptible d’exister. S’il existe une solution de temps polynomial possible, alors cette solution résout un gros problème d’informatique que de nombreux scientifiques essaient depuis des années.
Nous discuterons bientôt d’autres problèmes NP-Complets et de leur preuve de NP-Complétude.