Règle générale pour savoir si un problème pourrait être NP-complet

26

Cette question a été inspirée par un commentaire sur StackOverflow .

En plus de connaître les problèmes NP-complets du livre Garey Johnson, et bien d'autres; existe-t-il une règle empirique pour savoir si un problème ressemble à un problème NP-complet?

Je ne cherche pas quelque chose de rigoureux, mais quelque chose qui fonctionne dans la plupart des cas.

Bien sûr, chaque fois que nous devons prouver qu'un problème est NP-complet, ou une légère variante d'un NP-complet; mais avant de se précipiter vers la preuve, il serait bon d'avoir une certaine confiance dans le résultat positif de la preuve.

Виталий Олегович
la source
8
Ma règle d'or est simple: si ça ne sent pas comme un problème que je connais déjà, c'est probablement NP-difficile (ou pire).
JeffE
12
@JeffE bien sûr, vous connaissez déjà pas mal de problèmes ... les nouveaux arrivants sur CS peuvent ne pas être en mesure d'utiliser la même règle.
Joe
1
@Joe: C'est vrai. Il serait peut-être préférable de dire: si vous n'avez pas trouvé le problème dans un manuel, c'est probablement NP-difficile.
JeffE
2
Une autre façon de dire cela: c'est surprenant quand un problème n'est pas NP-difficile, plutôt que quand un problème est NP-difficile.
Joe

Réponses:

15

C'est mon approche personnelle pour déterminer si un problème (c'est-à-dire une langue ) est NP-complet ou non. Si ces deux conditions sont vérifiées:L

  • Je pense que tester si une instance est dans L implique que je dois vérifier toutes les combinaisonsIL
  • et qu'il n'y a aucun moyen de diviser une telle combinaison en deux plus petites

alors peut très bien être NP-dur.L

Par exemple pour le problème de la somme des sous - ensembles , je dois lister tous les sous-ensembles de et vérifier s'il y en a un dont la somme est nulle. Puis-je diviser S en deux sous-ensembles plus petits S 1 et S 2 sur lesquels je vérifierai une propriété similaire? Humm ... pas vraiment. Peut-être que si je vérifiais toutes les combinaisons de S 1 et S 2 mais ce serait vraiment long ...SSS1S2S1S2

Habituellement, la capacité de se diviser en petits morceaux est un bon indicateur d'un problème en P. C'est l' approche diviser pour mieux régner . Par exemple, pour trouver le chemin le plus court entre deux points, vous pouvez utiliser la propriété que si le chemin le plus court de à C passe par B, il n'est pas plus long que le chemin le plus court de A à B plus le plus court de BACBABB à .C

Franchement, cette approche est très basique: j'essaie de trouver un algorithme (polynomial) pour le problème donné. Si je n'en trouve pas, le problème devient "difficile" à mon avis. Vient ensuite tout le raisonnement NP-complétude: vais-je pouvoir encoder un problème NP-complete existant dans celui-ci? (Et comme c'est généralement beaucoup plus difficile, j'essaie encore une fois de trouver un algorithme polynomial ..)

Je soupçonne que c'est la façon de penser habituelle. Il reste cependant assez difficile à appliquer sur des problèmes inconnus. Je me souviens personnellement d'avoir été surpris par l'un des premiers exemples de complétude de NP qui m'a été dit: le problème de la clique . Cela semblait si simple à vérifier! Je suppose donc que cette expérience y est pour beaucoup. L'intuition peut aussi parfois être inutile. Je me souviens avoir entendu plusieurs fois deux problèmes presque identiques, mais l'un était en P et l'autre avec une petite variation était NP-complet.

Je n'ai pas encore trouvé de bon exemple (j'ai besoin d'aide ici), mais c'est comme le problème de la correspondance par correspondance : c'est un problème indécidable mais certaines variantes sont décidables.

jmad
la source
7
+1
2
Une exception intéressante à la règle de base est les problèmes d'optimisation qui peuvent être résolus avec une programmation linéaire. Si vous n'avez pas entendu parler de l'astuce, il peut être difficile de voir comment des problèmes tels que le problème d'affectation ou la correspondance de graphiques peuvent être résolus en temps poly, car les astuces comme diviser pour mieux régner et la programmation dynamique ne semblent pas s'appliquer.
hugomg
Un exemple est le problème de la séquence commune la plus longue qui est en P pour 2 séquences mais entre dans NP-Hard avec plus.
Christian Vielma
14

Une autre perspective sur la dureté du problème vient de la communauté des jeux et des casse-têtes, où la règle de base est que `` les problèmes sont aussi difficiles qu'ils peuvent l'être '' (et les exceptions proviennent de structures cachées dans le problème - l'exemple de Massimo du déterminant dans commentaires en est un bon exemple); l'astuce consiste alors à comprendre à quel point un problème peut être difficile:

  • n polyominos peut-il emballer un rectangle donné de la zone appropriée?) est NP-complet.
  • Les énigmes impliquant une séquence de mouvements dans un espace d'états délimité se trouvent dans PSPACE (puisque `` l'arbre de déplacement '' peut généralement être exploré de manière standard en profondeur d'abord ne nécessitant qu'un stockage pour un nombre polynomial de configurations), et ont tendance à être PSPACE complet; un exemple classique de cela est Rush Hour.
  • Les jeux avec une profondeur délimitée polynomialement sont également dans PSPACE; cela utilise la caractérisation de PSPACE comme APTIME, car la caractérisation min-max habituelle des stratégies imite parfaitement une machine de Turing alternée avec sa caractérisation comme `` il existe un mouvement pour le joueur A tel que pour chaque mouvement de réponse du joueur B, il existe une réponse se déplacer pour le joueur A de telle sorte que ... ', etc. Ils ont également tendance à être PSPACE-complete; Les jeux hexadécimaux et Tic-Tac-Toe généralisés en sont des exemples.
  • Les jeux sans limite sur la profondeur de l'arbre mais joués dans un espace délimité (polynomialement) sont dans EXPTIME, car il y a exponentiellement beaucoup de positions totales et le graphique entier peut être construit et exploré en polynôme temporel dans le nombre de positions (et donc exponentiel global) ; ces jeux sont généralement complets pour EXPTIME. Les échecs, les dames et le go entrent tous dans cette catégorie.
Steven Stadnicki
la source