Pourquoi la classe NP-Complete est-elle importante par rapport à NP-hard?

J'étudie la complexité informatique et je me demandais pourquoi les problèmes NP-Complete (NPC) sont une classe importante. Je trouve évident pourquoi nous voulons montrer qu'un problème de NP donné est NP-difficile.

Je comprends également la définition de NPC, et que montrer un problème de décision donné est NP-difficile, sachant qu'il est en NP, était exactement le moyen NPC.

Cependant, ce que je ne comprends pas, c'est: pourquoi ce concept est-il si important? Assurément, si l' on trouve tout algorithme NP-dur qui fonctionne en temps P (ou non qui est en NP), nous avons montré que .$NP = P$

Pourquoi ce concept est-il si important?

Il y a au moins quelques raisons pour lesquelles NPC est intéressant:

• La classe NP contient de nombreux problèmes qui sont intéressants (à la fois sur le plan pratique et théorique), de plus, beaucoup de ces problèmes se révèlent être NP-difficiles (et donc NP-complets), mais de nombreux problèmes en dehors de NP sont presque certainement trop difficiles à résoudre. plus qu'un intérêt théorique , NPC fournit donc un groupe (approximatif) de problèmes qui sont apparemment difficiles, mais pas si difficiles que nous ne pouvons pas essayer de faire quelque chose avec eux.
  En d'autres termes, le NPC est probablement la limite de ce que nous pouvons espérer résoluble en temps polynomial, il semblerait difficile d'essayer pour PSPACE = P (par exemple).
• La classe NP est structurellement intéressante. C'est l'exemple de base de "obtenons-nous plus de" vitesse "de calcul du non-déterminisme". Nous sommes donc intéressés de savoir si P = NP ou non, et NPC est (probablement) un élément important de l'élaboration de cela.
• NP-hard (en tant que classe) est vraiment trop grand et varié pour être traité comme une seule chose, c'est tout ce qui peut être réduit à un problème NP-complet , y compris un énorme éventail de choses en dehors de NP, donc du point de vue de vue d'essayer de développer des résultats et des techniques générales, il n'y a rien à saisir.

Du point de vue de quelqu'un qui écrit du code pour vivre, il est important d'avoir une bonne connaissance de l'exhaustivité de NP pour:

1. Reconnaître quand vous aboyez le mauvais arbre

Les problèmes NP-complets sont les plus difficiles des problèmes NP-difficiles et pourtant, pour autant que nous puissions en juger, il faut du temps exponentiel à la taille de l'entrée pour résoudre un tel problème de décision. Donc, en pratique, si vous pouvez montrer que le problème que vous essayez de résoudre est NP-difficile (généralement en montrant qu'une solution efficace à cela donnerait également une solution efficace à un problème NP-complet), vous savez que vous pouvez arrêter de rechercher un algorithme efficace pour le résoudre exactement en général. Au lieu de cela, vous pouvez choisir parmi des algorithmes connus qui promettent de bonnes approximations pour les problèmes d'optimisation NP-hard et poursuivre le reste de votre projet.

2. Trouver le bon arbre

Parce que les ordinateurs sont souvent utilisés pour attaquer les problèmes NP-hard, des solveurs spécialisés ont été développés qui peuvent résoudre efficacement certaines instances de problèmes NP-hard. Reconnaître que votre problème est NP-complet est la première étape vers la recherche d'un outil existant (SAT, ILP, SMT, CSP pour n'en nommer que quelques-uns) qui pourrait vous aider à trouver des solutions exactes dans certains cas où vous auriez autrement dû vous contenter d'un approximation.

"Sûrement, si nous trouvons un algorithme NP-dur qui s'exécute dans le temps P (que ce soit ou non dans NP), nous avons montré que NP = P. Pourquoi ce concept est-il si important?"

Chaque problème NP se réduit à n'importe quel problème NPC, mais ce n'est pas vrai que chaque problème NP se réduit à n'importe quel problème NP-dur, donc prouver qu'un algorithme NP-hard est en P ne prouve pas du tout P = NP. Ce serait le cas, cependant, pour un problème de PNJ, c'est précisément ce que "réduit" signifie. Donc, si nous trouvons un algorithme P pour un problème NPC, alors, nous aurons prouvé que P = NP.