human
Suppose que je suis un programmeur et que j'ai un problème NP-complet que je dois résoudre. Quelles méthodes sont disponibles pour traiter les problèmes NPC ? Y a-t-il une enquête ou quelque chose de similaire sur ce sujet
gpt
Il existe plusieurs stratégies bien étudiées ; celle qui convient le mieux à votre application dépend des circonstances.

* Améliorer le temps d'exécution dans le pire des cas
En utilisant des connaissances spécifiques au problème, vous pouvez souvent améliorer l'algorithme naïf. Par exemple, il existe des algorithmes en $O(c^n)$ pour le problème du Vertex Cover avec $c$ une amélioration considérable par rapport à l'algorithme naïf en $\Omega(2^n)$, ce qui peut rendre les tailles d'instances gérables pour vous.

* Améliorer le temps d'exécution attendu
En utilisant des heuristiques, vous pouvez souvent concevoir des algorithmes rapides pour de nombreuses instances. Si celles-ci incluent la plupart des cas que vous rencontrez dans la pratique, vous êtes gagnant. Des exemples sont SAT pour lesquels des solveurs assez complexes existent, et l'algorithme du Simplex (qui résout un problème polynomial, mais quand même). Une technique de base souvent utile est la méthode de branch and bound.

* Restreindre le problème
Si vous pouvez faire plus d'hypothèses sur vos entrées, le problème peut devenir facile.

* Propriétés structurelles
Vos entrées peuvent avoir des propriétés qui simplifient la résolution du problème, par exemple la planarité, la bipartition ou l'absence d'un mineur pour les graphes. Consultez ici quelques exemples de classes de graphes pour lesquelles CLIQUE est facile.

* Fonctions bornant l'entrée
Une autre chose à examiner est la complexité paramétrée ; certains problèmes sont solubles en temps $O(2^kn^m)$ pour $k$ un paramètre de l'instance (degré maximum des nœuds, poids maximum des arêtes, ...) et $m$ constant. Si vous pouvez borner $k$ par une fonction polylogarithmique en $n$ dans votre contexte, vous obtenez des algorithmes polynomiaux. Saeed Amiri donne des détails dans sa réponse.

* Quantités bornant l'entrée
De plus, certains problèmes admettent des algorithmes qui s'exécutent en temps pseudo-polynomial, c'est-à-dire que leur temps d'exécution est borné par une fonction polynomiale d'un nombre faisant partie de l'entrée ; le test naïf de primalité en est un exemple. Cela signifie que si les quantités encodées dans vos instances ont une taille raisonnable, vous pouvez avoir des algorithmes simples qui se comportent bien pour vous.

* Affaiblir le résultat
Cela signifie que vous tolérez des résultats erronés ou incomplets. Il existe deux principales variantes :

* Algorithmes probabilistes
Vous n'obtenez le résultat correct qu'avec une certaine probabilité. Il existe plusieurs variantes, les plus connues étant les algorithmes de Monte-Carlo et Las-Vegas. Un exemple célèbre est le test de primalité de Miller-Rabin.

* Algorithmes d'approximation
Vous ne recherchez plus des solutions optimales mais presque optimales. Certains algorithmes admettent des bornes relatives ("pas plus de deux fois l'optimum"), d'autres des bornes absolues ("pas plus de $5$ plus l'optimum") sur l'erreur. Pour de nombreux problèmes, il est encore ouvert de savoir dans quelle mesure ils peuvent être approximés. Certains peuvent être approximés de manière arbitrairement précise en temps polynomial, tandis que d'autres sont connus pour ne pas le permettre ; consultez la théorie des schémas d'approximation en temps polynomial.

Consultez Algorithmics for Hard Problems de Hromkovič pour un traitement approfondi.
* Simplicity is beauty: Improved upper bounds for vertex cover de Chen Jianer, Iyad A. Kanj, Ge Xia (2005)