Pourquoi est-il important de prouver qu'un problème est NP-complet?

Ai-je raison de comprendre que prouver un problème NP complet est un succès en recherche? Si oui, pourquoi?

Ali, bonne question.

Supposons que vous vouliez montrer qu'un problème P est difficile à calculer. Maintenant, vous pourriez conjecturer que P est difficile simplement parce que nous n'avons pas encore d'algorithmes efficaces pour cela. Mais ce sont des preuves plutôt fragiles, non? Il se pourrait que nous ayons manqué une belle façon de voir P qui serait très facile à résoudre. Donc, afin de conjecturer que P est difficile, nous voudrions accumuler plus de preuves. Les réductions fournissent un outil pour faire exactement cela! Si nous pouvons réduire un autre problème naturel Q en P, alors nous avons montré que P est au moins aussi difficile que Q. Mais Q pourrait être un problème provenant d'un domaine mathématique complètement différent, et les gens peuvent avoir lutté pendant des décennies pour résoudre Q également. . Ainsi, nous pouvons voir notre échec à trouver un algorithme efficace pour que Q soit la preuve que P est difficile. Si nous avons beaucoup de tels Q '

C'est exactement ce que fournit la théorie de l'exhaustivité de NP. Si vous prouvez que votre problème est NP-complet, alors vous avez lié sa dureté à la dureté de centaines d'autres problèmes, chacun présentant un intérêt significatif pour diverses communautés. Ainsi, moralement parlant, vous pouvez être assuré que votre problème est effectivement difficile.

Prouver un problème NP-Complete est un succès de recherche car il vous évite d'avoir à rechercher une solution efficace et exacte pour le problème général que vous étudiez. Cela prouve que votre problème appartient à une classe de problèmes si difficile que personne n'a pu trouver d'algorithme efficace et exact pour aucun des problèmes, et une telle solution pour l'un des problèmes impliquerait une solution pour tous les problèmes. problèmes.

Il s'agit généralement d'un tremplin, car votre problème est toujours là - vous devez simplement assouplir vos exigences. Habituellement, les gens essaient de trouver un moyen de relâcher une ou plusieurs méthodes «efficaces», «exactes» ou «générales». Inefficace-et-exact-et-général est la tentative de trouver de meilleures constantes dans l'exposant pour ces algorithmes. Efficace et inexacte et générale est l'étude des algorithmes d'approximation. Efficace et exacte mais non générale est l'étude de la tractabilité à paramètres fixes et la recherche de sous-classes d'entrée pour lesquelles des algorithmes efficaces peuvent être trouvés.

Voyons deux cas différents pour lesquels deux personnes différentes voudraient prouver un problème $NP-complete$

a) Vous travaillez sur un projet logiciel. Après avoir spécifié votre système, vous commencez à définir l'architecture de votre application. Cela comprend la décomposition du problème / besoin important que l'application sert à des problèmes plus petits. Disons que vous avez été chargé de trouver un algorithme efficace (nous ne voulons pas que notre application soit lente!) Pour l'un de ces petits problèmes. Après avoir lutté pendant un certain temps, vous ne pouvez pas trouver d'algorithme polynomial. Alors vous pourriez penser: peut-être que ce problème est très difficile, il est donc très difficile (voire impossible) de trouver un algorithme efficace. En prouvant que le problème est$NP-complete$, vous avez des preuves de votre conjecture et vous devriez commencer à envisager une approche alternative (par exemple, en modifiant le problème afin qu'il devienne plus facile).

$NP-complete$

$NP-complete$

$P=NP$$3-SAT$

$NP-complete$$CLIQUE$

Résumer, caractériser un problème vous permet d'utiliser des techniques courantes. En étudiant la classe à laquelle il est lié, vous pouvez penser à un niveau abstrait, sans vous soucier des spécificités de ce problème particulier, courant en mathématiques et en sciences en général. Travailler avec des classes au lieu de membres individuels vous permet d'utiliser des techniques connues et, en outre, d'appliquer vos connaissances à un plus grand nombre d'objets, au lieu d'un seul.

Chaque problème a plusieurs connexions avec d'autres problèmes. De plus, il existe des relations entre un problème et des classes de complexité.

Par conséquent, classer un problème en tant que NPC nous donne généralement un aperçu d'autres problèmes, ainsi que des classes de complexité.

Par exemple, prenons le problème de l' isomorphisme graphique (GI). Dans l'article suivant:

Uwe Schöning, l' isomorphisme graphique est dans la basse hiérarchie , Actes du 4e Symposium annuel sur les aspects théoriques de l'informatique , 1987, 114–124; aussi: Journal of Computer and System Sciences, vol. 37 (1988), 312–323.

il est prouvé que si GI ∈ NPC, alors la hiérarchie polynomiale (PH) s'effondre à son deuxième niveau; qui sera une percée majeure dans la théorie de la complexité structurelle.

$p$$p$$p$$p$