Comment puis-je construire des réductions entre les problèmes pour prouver qu'un problème est NP-complet?

27

Je prends un cours de complexité et j'ai du mal à trouver des réductions entre les problèmes de PNJ. Comment puis-je trouver des réductions entre les problèmes? Y a-t-il une astuce générale que je peux utiliser? Comment dois-je aborder un problème qui me demande de prouver qu'un problème est un PNJ?

Anonyme
la source
4
Désolé de décevoir, je ne pense pas qu'il existe une méthode qui résout tout. Comme beaucoup de problèmes dans la vie, chacun est unique. Avec le temps, vous aurez la bonne idée de comment les résoudre.
Ran G.
1
Existe-t-il des directives utiles sur la façon d'aborder ces problèmes? Je suis complètement perdu quand je vois une question qui me demande de prouver que c'est un PNJ. Comment dois-je les approcher?
Anonyme

Réponses:

45

Il n'y a pas de solution miracle; Les épreuves de dureté NP sont dures. Cependant, il existe un cadre général pour toutes ces preuves. De nombreux étudiants qui éprouvent des difficultés avec les preuves de dureté NP sont confus quant à ce qu'ils sont censés faire, ce qui rend évidemment impossible de comprendre comment le faire. Voici donc quoi faire pour prouver un problème NP-difficile.

Tout d'abord, à moins que vous ne fassiez vos devoirs, vous devez décider quel problème NP-difficile réduire à votre problème . C'est en grande partie une question d'odorat. Si le nombre 3 apparaît n'importe où dans l'énoncé du problème, essayez de réduire de ou ou . (Oui, je suis sérieux.) Si votre problème implique de trouver une sous-séquence, une permutation ou un chemin optimal, essayez de réduire à partir de ou . Si votre problème demande le plus petit sous-ensemble avec une certaine propriété, essayez ; s'il demande le plus grand sous-ensemble avec une certaine propriété, essayez3 C o l o r 3 P a r t i t i o n H a m i l t o n i a n C y c l e H a m i l t o n i a n P a t h C l i q u e I n d e3SAT3Color3PartitionHamiltonianCycleHamiltonianPathCliqueIndependentSet. Si votre problème implique de faire quelque chose dans l'avion, essayez ou . Etc. Si votre problème ne "sent" rien, ou est probablement votre meilleur choix.P l a n a r T S P 3 S A T C i r c u i t S A TPlanarCircuitSATPlanarTSP3SATCircuitSAT

De toute évidence, vous devez déjà savoir précisément comment tous ces problèmes sont définis , et plus le problème est simple, mieux c'est. Donc, aussi cool que le résultat puisse paraître à la fin, je ne recommande pas de réduire de ou ou ou .MinesweeperTetrisOneCheckersMoveSuperMarioBros

Deuxièmement, la réduction réelle. Pour réduire le problème X (celui que vous connaissez est NP-difficile) au problème Y (celui que vous essayez de prouver est NP-difficile, vous devez décrire un algorithme qui transforme une instance arbitraire de X en une instance légale de Y L'algorithme de réduction doit faire quelque chose de spécifique avec chaque "fonctionnalité" de l'instance X, la partie de la sortie pour chaque "fonctionnalité" est généralement appelée gadget .

Mais qu'est-ce qu'une fonctionnalité? Cela dépend du problème X. Par exemple:

  • Pour transformer une instance de , vous aurez besoin d'un gadget pour chaque variable et pour chaque clause dans la formule d'entrée. Chaque gadget variable doit avoir deux "états" qui correspondent à "vrai" et "faux". Chaque gadget de clause doit également avoir plusieurs "états", chacun obligeant d'une manière ou d'une autre au moins l'un des littéraux de cette clause à être vrai. (Les états ne font pas partie de la sortie de l'algorithme de réduction.)3SAT

  • Pour transformer une instance de , vous aurez besoin d'un gadget pour chaque sommet et chaque bord du graphique d'entrée, et d'un autre gadget pour définir les trois couleurs.3Color

  • Pour transformer une instance de , vous aurez besoin d'un gadget pour chaque entrée, pour chaque fil et pour chaque porte du circuit d'entrée.PlanarCircuitSat

La forme réelle du gadget dépend de problème Y, celui que vous réduisez à . Par exemple, si vous réduisez à un problème concernant les graphiques, vos gadgets seront de petits sous-graphiques; voir l'article Wikipedia. Si vous réduisez à un problème de planification, chaque gadget sera un ensemble de tâches à planifier. Si vous vous réduisez à un problème concernant Mario , chaque gadget sera un ensemble de blocs, de briques et de Koopas.

Cela peut devenir déroutant si les deux problèmes impliquent le même type d'objet. Par exemple, si X et Y posent tous les deux des problèmes avec les graphiques, votre algorithme va transformer un graphique (une instance de X) en un graphique différent (une instance de Y). Choisissez judicieusement votre notation, afin de ne pas confondre ces deux graphiques. Je recommande également fortement d'utiliser plusieurs couleurs d'encre.

Enfin, votre algorithme de réduction doit satisfaire trois propriétés:

  • Il s'exécute en temps polynomial. (C'est généralement facile.)

  • Si votre algorithme de réduction reçoit une instance positive de X en entrée, il produit une instance positive de Y en sortie.

  • Si votre algorithme de réduction produit une instance positive de Y en sortie, il doit avoir reçu une instance positive de X en entrée.

Il y a ici une subtilité importante. Votre algorithme de réduction ne fonctionne que dans une seule direction, des instances de X aux instances de Y, mais pour prouver que l'algorithme est correct, il faut raisonner sur la transformation dans les deux directions. Vous devez également vous rappeler que votre algorithme de réduction ne peut pas dire si une instance donnée de X est positive ou négative - cela nécessiterait de résoudre un problème NP-difficile en temps polynomial!

Voilà le quoi . Le comment vient avec la pratique.

JeffE
la source
5
Pour les réductions de (et généralement des problèmes qui ont une "structure locale / globale" similaire), il pourrait être judicieux d'essayer de le faire en premier pour des instances de clause unique de . Cela peut vous donner une idée du gadget que vous devez utiliser pour les clauses. Après avoir découvert le gadget d'une clause, votre réduction mettra l'un de ces gadgets pour chaque clause, puis appliquera d'une manière ou d'une autre la condition globale (c'est-à-dire que les valeurs de vérité pour les occurrences d'une variable apparaissant dans différentes clauses doivent être cohérentes, une variable propositionnelle ne peut pas être dans une clause et dans une autre). 3 S A T p t r u e f a l s e3SAT3SATptruefalse
Kaveh
1
Concernant "Si votre algorithme de réduction produit une instance positive de Y en sortie, il doit avoir reçu une instance positive de X en entrée": Bien qu'il semble plus intuitif d'écrire cette condition comme "Si votre algorithme de réduction reçoit une instance négative de X en entrée, il produit une instance négative de Y en sortie ", notez que ces deux conditions sont équivalentes , et comment JeffE l'a écrit rend généralement la construction de la preuve beaucoup plus facile, car dans chaque cas vous" avez quelque chose "(soit le instance positive de X, ou l'instance positive de Y) avec laquelle travailler.
j_random_hacker
11

JeffE décrit la stratégie la plus courante: connaître de nombreux problèmes NP-complets, en trouver un qui correspond très bien et effectuer la réduction facile .

Une autre stratégie valable consiste à toujours utiliser 3SAT (ou tout autre problème). Cela pourrait rendre certaines réductions plus complexes, mais le côté positif est que vous avez beaucoup d'expérience pour exprimer la satiabilité dans d'autres types de problèmes. Vous gagnez ainsi du temps à trouver un bon partenaire de réduction (y compris les impasses) et espérez que votre expérience vous permettra de faire la réduction rapidement même si elle est plus difficile.

Cette approche a aussi une méta beauté: (3) SAT est l'un des rares problèmes pour lesquels l'exhaustivité de NP a été prouvée (presque) directement. Par conséquent, s'appuyer uniquement sur cette preuve maintient votre "arbre de preuve" à plat, évitant de longues chaînes de réductions.

Raphael
la source
3
Directement prouvant que le problème Borné Stopper est NP-complet quand la limite est donnée dans unaire est pas trop dur, et est un moyen facile de prouver que certains problèmes NP-complet existe, même si le problème lui - même est plutôt inutile de réduire de.
Alex ten Brink
3
Je ne suis pas sûr de l'affirmation selon laquelle c'est le seul problème qui s'est avéré être NP-complet directement. En fait, si vous l'interprétez au sens strict, c'est définitivement faux. L'article de Cook de 1971 parle de TAUT pas SAT (il utilise des réductions Cook, pas des réductions Karp) (il est facile d'observer que la preuve prouve également que SAT est NP-complet sous les réductions Karp).
Kaveh
@Kaveh Huh? La tautologie est Co-Np complète et n'est donc pas connue pour être en NP (-complète). Je n'ai pas lu le papier de Cook cependant.
Albert Hendriks
1
@Albert, alors tu devrais le lire alors. Avec les réductions Cook, vous ne pouvez pas faire la distinction entre NP et coNP.
Kaveh