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

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?

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 $\mathsf{3SAT}$$\mathsf{3Color}$$\mathsf{3Partition}$$\mathsf{HamiltonianCycle}$$\mathsf{HamiltonianPath}$$\mathsf{Clique}$$\mathsf{IndependentSet}$. 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 $\mathsf{PlanarCircuitSAT}$$\mathsf{PlanarTSP}$$\mathsf{3SAT}$$\mathsf{CircuitSAT}$

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 .$\mathsf{Minesweeper}$$\mathsf{Tetris}$$\mathsf{OneCheckersMove}$$\mathsf{SuperMarioBros}$

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.)$\mathsf{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.$\mathsf{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.$\mathsf{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 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.