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

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.

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 combinaisons$I$$L$
• 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 ...$S$$S$$S_1$$S_2$$S_1$$S_2$

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 $A$$C$$B$$A$$B$$B$ à .$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.

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.