Pourquoi n'y a-t-il pas d'algorithmes d'approximation pour SAT et d'autres problèmes de décision?

18

J'ai un problème de décision NP-complet. Étant donné une instance du problème, je voudrais concevoir un algorithme qui génère OUI, si le problème est réalisable, et NON, sinon. (Bien sûr, si l'algorithme n'est pas optimal, il fera des erreurs.)

Je ne trouve aucun algorithme d'approximation pour de tels problèmes. Je cherchais spécifiquement SAT et j'ai trouvé dans la page Wikipédia sur l' algorithme d'approximation ce qui suit: Une autre limitation de l'approche est qu'elle ne s'applique qu'aux problèmes d'optimisation et non aux problèmes de décision "purs" comme la satisfiabilité, bien qu'il soit souvent possible de .. .

Pourquoi ne définissons-nous pas, par exemple, le rapport d'approximation comme quelque chose de proportionnel au nombre d'erreurs que l'algorithme commet? Comment résoudre réellement les problèmes de décision de manière gourmande et sous-optimale?

Ribz
la source
5
Il existe des algorithmes d'approximation pour MAX-SAT.
Yuval Filmus
2
MAX-SAT n'est pas un problème de décision, non?
Ribz
15
Les algorithmes d'approximation sont toujours destinés aux problèmes d'optimisation.
Yuval Filmus
4
Donc, vous voulez essentiellement avoir un algorithme qui se termine rapidement mais qui peut occasionnellement donner la mauvaise réponse. Je pense que vous confondez énormément les problèmes en utilisant des termes bien définis comme «algorithme d'approximation» et «optimal» ici. Celles-ci ont des significations très spécifiques. Je suppose que vous recherchez plutôt une heuristique - si vous mettez à jour votre question avec ce terme (ou recommencez à zéro avec une nouvelle question pour éviter encore plus de confusion), vous pourriez avoir de meilleurs résultats.
AnoE
Bien que ce ne soit pas une réponse complète, cela explique en partie la raison: il existe des problèmes SAT importants pour lesquels avoir seulement le mauvais bit mal n'est pas mieux que d'avoir la moitié des bits mal.
Joshua

Réponses:

33

Les algorithmes d'approximation sont uniquement destinés aux problèmes d'optimisation, pas aux problèmes de décision.

Pourquoi ne définissons-nous pas le rapport d'approximation comme la fraction d'erreurs qu'un algorithme commet, lorsqu'il essaie de résoudre un problème de décision? Parce que "le rapport d'approximation" est un terme avec une signification standard bien définie, qui signifie autre chose, et il serait déroutant d'utiliser le même terme pour deux choses différentes.

OK, pourrions-nous définir un autre ratio (appelons-le quelque chose d'autre - par exemple, "le ratio det") qui quantifie le nombre d'erreurs qu'un algorithme fait, pour un problème de décision? Eh bien, on ne sait pas comment procéder. Quel serait le dénominateur de cette fraction? Ou, pour le dire autrement: il va y avoir un nombre infini d'instances problématiques, et pour certaines d'entre elles, l'algorithme donnera la bonne réponse et d'autres il donnera la mauvaise réponse, donc vous vous retrouvez avec un ratio qui est "quelque chose divisé par l'infini", et qui finit par être dénué de sens ou non défini.

Alternativement, nous pourrions définir comme étant la fraction des erreurs des erreurs d'algorithme, sur les instances de problème de taille n . Ensuite, nous pourrions calculer la limite de r n comme n , si une telle limite existe. Ce seraitrnnrnnêtre bien défini (si la limite existe). Cependant, dans la plupart des cas, cela pourrait ne pas être très utile. En particulier, il suppose implicitement une distribution uniforme sur les instances de problème. Cependant, dans le monde réel, la distribution réelle des instances à problème peut ne pas être uniforme - elle est souvent très loin d'être uniforme. Par conséquent, le nombre que vous obtenez de cette manière n'est souvent pas aussi utile que vous pourriez l'espérer: il donne souvent une impression trompeuse de la qualité de l'algorithme.

Pour en savoir plus sur la façon dont les gens gèrent l'intractabilité (dureté NP), jetez un coup d'œil à Gérer l'intractabilité: problèmes NP-complets .

DW
la source
3
+1. Mais le dernier point n'est pas solide, on pourrait dire que vous pouvez définir le rapport d'approximation comme la limite lorsque n va à l'infini du nombre d'erreurs que le programme fait en entrée de longueur n sur le nombre de chaînes de longueur n. Bien sûr, cela ne s'avère pas utile, car souvent un simple programme qui sort juste "OUI" (ou "NON") atteint un bon rapport (parfois même 1!).
aelguindy
1
@det, c'est une question distincte, que vous devriez poser séparément (après avoir lu à ce sujet dans les manuels standard ou les ressources en ligne). Nous préférons que vous posiez une seule question par message.
DW
1
@aelguindy, bon point. J'ai mis à jour ma réponse en conséquence.
DW
2
@det Pourquoi gourmand? Que signifie «presque» résoudre un problème de décision?
Raphael
2
@Mehrdad: Habituellement, vous évaluez un algorithme d'approximation par son erreur la plus défavorable: une limite supérieure sur la façon dont il n'est jamais optimal. Ainsi, par exemple, vous pourriez dire qu'un algorithme d'approximation donné trouve toujours un résultat qui représente au moins cinq sixièmes du résultat optimal. Il n'y a aucun moyen réel de traduire cela en un problème de décision; si votre algorithme émet parfois (disons) 0,1, alors soit il est parfois désactivé de 0,9 (auquel cas vous feriez mieux, dans le pire des cas, d'émettre toujours 0,5), soit l'état "approximatif" est une imposture et "0,1 "signifie simplement" 0 ".
ruakh
14

La raison pour laquelle vous ne voyez pas des choses comme les ratios d'approximation dans les problèmes de prise de décision est qu'ils n'ont généralement pas de sens dans le contexte des questions que l'on pose généralement sur les problèmes de prise de décision. Dans un paramètre d'optimisation, cela a du sens car il est utile d'être «proche». Dans de nombreux environnements, cela n'a pas de sens. Cela n'a pas de sens de voir à quelle fréquence vous êtes "proche" dans un problème de logarithme discret. Cela n'a pas de sens de voir à quelle fréquence vous êtes "proche" de trouver un isomère graphique. Et de même, dans la plupart des problèmes de prise de décision, il n'est pas logique d'être «proche» de la bonne décision.

Maintenant, dans les implémentations pratiques, il existe de nombreux cas où il est utile de savoir quelle partie des problèmes peut être résolue "rapidement" et quelle partie ne peut pas l'être. Cependant, contrairement à l'optimisation, il n'y a pas de moyen unique de quantifier cela. Vous pouvez le faire statistiquement, comme vous le suggérez, mais seulement si vous connaissez la distribution statistique de vos entrées. La plupart du temps, les gens qui s'intéressent aux problèmes de décision ne sont pas aussi chanceux d'avoir de telles distributions.

Comme étude de cas, considérons le problème de l'arrêt. Le problème de l'arrêt est connu pour être indécidable. C'est dommage, car c'est un problème vraiment utile à résoudre si vous faites un compilateur. En pratique, cependant, nous constatons que la plupart des programmes sont en fait très faciles à analyser du point de vue de l'arrêt du problème. Les compilateurs en profitent pour générer un code optimal dans ces circonstances. Cependant, un compilateur doit reconnaître qu'il existe une possibilité qu'un bloc de code particulier ne soit pas décidable. Tout programme qui repose sur un code «probablement décidable» peut avoir des problèmes.

Cependant, la métrique utilisée par les compilateurs pour déterminer leur capacité à résoudre ces cas particuliers du problème d'arrêt est très différente d'une métrique utilisée par un programme de cryptographie pour tester si une paire particulière de nombres premiers est durablement acceptée contre les attaques. Il n'y a pas de solution unique. Si vous voulez une telle métrique, vous voudrez l'adapter à votre espace de problèmes et à votre logique métier.

Cort Ammon - Rétablir Monica
la source
Donc, si je comprends bien, la seule façon de résoudre un problème de décision est de concevoir l'algorithme optimal qui peut être très inefficace? Parce que j'ai un problème de décision (NP-complet) et on m'a demandé de trouver un algorithme gourmand (rapide) pour trouver une solution. Comment puis-je résoudre ça? Connaissez-vous un article portant sur ce type de problèmes?
Ribz
1
@det Repoussez et obtenez le problème reformulé. Si vous avez un problème NP-complet, vous êtes plutôt coincé, mais il est fort probable que vous n'ayez pas réellement besoin de le résoudre. Par exemple, vous n'avez pas toujours besoin de la réponse parfaite. Peut-être que fermer est assez bon. Ou peut-être pouvez-vous résoudre le problème pour un sous-ensemble de cas qui sont faciles, et vous lancer sur ceux qui sont difficiles. Par exemple, les algorithmes d'empaquetage sont souvent NP-complets, mais les algorithmes qui atteignent de manière fiable 5% de l'optimal en utilisant des approches probabalistes sont courants.
Cort Ammon - Rétablir Monica
2
En toute honnêteté, se faire dire de proposer un algorithme gourmand pour résoudre un programme NP-complet équivaut littéralement à être chargé d'assumer à lui seul l'ensemble de la communauté informatique / mathématique. Si vous trouvez un algorithme pour un programme complet NP-P dans le temps, au très moins vous gagnez le 1 million $ prix d'argile pour la résolution P = NP. En réalité, les effets de votre découverte remodèlent l'informatique telle que nous la connaissons et bouleversent complètement l'industrie de la sécurité / cryptographie du jour au lendemain. Mieux vaut que le libellé de la tâche soit ajusté pour ne pas être prouvé NP-complet.
Cort Ammon - Rétablir Monica
J'ai utilisé un algorithme exact gourmand pour un problème NP-complet. Je n'avais besoin que de résoudre un petit cas et j'ai pu obtenir un serveur à 64 processeurs pour un week-end.
Patricia Shanahan
8

En plus des réponses existantes, permettez-moi de souligner qu'il existe des situations où il est logique d'avoir une solution approximative pour un problème de décision, mais cela fonctionne différemment que vous ne le pensez.

Avec ces algorithmes, un seul des deux résultats est déterminé avec certitude, tandis que l'autre peut être incorrect. Prenez le test de Miller-Rabin pour les nombres premiers , par exemple: si le test détermine qu'un nombre n'est pas premier, ce résultat est certain. Mais dans l'autre cas, cela signifie seulement que le nombre est probablement premier. Selon le temps de calcul que vous êtes prêt à investir, vous pouvez augmenter votre confiance dans le résultat, mais ce ne sera pas 100% comme pour le cas non-prime.

Ceci est particulièrement puissant lors de la résolution de problèmes indécidables: vous pouvez écrire un outil qui tente de résoudre le problème d'arrêt pour un morceau de code spécifique. S'il peut trouver une preuve que le programme ne bouclera pas indéfiniment, vous pouvez le réclamer avec une certitude à 100%. Si vous ne pouvez pas trouver une telle preuve, il se peut que le flux de contrôle du programme soit trop alambiqué pour que votre outil puisse l'analyser, mais ce n'est pas une preuve qu'il bouclera pour toujours. En simplifiant les structures de contrôle, vous pourriez être en mesure de créer un programme équivalent suffisamment simple pour que l'outil prouve qu'il s'arrêtera à coup sûr.

ComicSansMS
la source
Il y a une grande différence entre les algorithmes probabilistes (votre réponse) et d'approximation (la question). En particulier, la combinaison des deux est une race très spéciale.
Raphael
De plus, nous savons que les algorithmes probabilistes pour le problème d'arrêt n'existent pas, en supposant une interprétation raisonnable du terme dans ce contexte.
Raphael
@Raphael Je ne voulais pas que ma réponse soit spécifique aux algorithmes probabilistes. Certes, pour Miller-Rabin, c'est le cas, mais comme vous l'avez mentionné vous-même, ce n'est plus vrai pour l'exemple du problème d'arrêt, et je suppose que ce ne sera pas le cas non plus pour la majorité des cas où vous trouverez ce comportement. Le point que je voulais faire passer est simplement que vous n'obtiendrez de certitude que sur un résultat, mais pas sur l'autre.
ComicSansMS
Si vous ne dites pas plus que certains problèmes ne sont que semi-calculables, je ne pense pas que vous répondiez à la question.
Raphael
@Raphael Ma réponse n'est pas non plus spécifique aux problèmes semi-calculables. En fait, je ne pense pas que l'approche que j'ai décrite s'applique même aux problèmes semi-calculables. Là, vous serez maintenant certain que vous avez atterri dans la branche non définie de la fonction, vous pouvez donc affirmer avec certitude qu'il n'y a pas de résultat. Ce que j'ai décrit se résume à: Il pourrait y avoir une réponse, mais l'algorithme n'a peut-être pas semblé assez difficile pour tomber dessus.
ComicSansMS