Dans la théorie de la calculabilité et de la complexité (et peut-être dans d'autres domaines), les réductions sont omniprésentes. Il en existe de nombreuses sortes, mais le principe reste le même: montrez qu'un problème est au moins aussi complexe qu'un autre problème en mappant des instances de à des solutions équivalentes à la solution . Essentiellement, nous montrons que tout résolveur pour peut également résoudre si nous lui permettons d'utiliser la fonction de réduction en tant que pré-processeur.L 2 L 2 L 1 L 1 L $L_1$$L_2$$L_2$$L_1$$L_1$$L_2$

J'ai réalisé ma part de réductions au fil des ans et quelque chose ne cesse de m'embêter. Bien que chaque nouvelle réduction nécessite une construction (plus ou moins) créative, la tâche peut sembler répétitive. Existe-t-il un pool de méthodes canoniques?

Quelles sont les techniques, modèles et astuces que l’on peut utiliser régulièrement pour construire des fonctions de réduction?

^{Ceci est supposé devenir une question de référence . Veillez donc à donner des réponses générales, présentées de manière didactique, illustrées par au moins un exemple mais couvrant néanmoins de nombreuses situations. Merci!}

Le cas particulier

Supposons que nous voulons montrer par rapport à une certaine notion de réduction R . Si L 1 est un cas particulier de L 2 , c'est assez trivial: on peut essentiellement utiliser la fonction identité. L'intuition derrière cela est claire: le cas général est au moins aussi difficile que le cas spécial.$L_1 \leq_R L_2$$R$$L_1$$L_2$

En "pratique", on nous donne et nous nous retrouvons avec le problème de choisir un bon partenaire de réduction L 1 , c’est-à-dire de trouver un cas particulier de L 2 qui s’est avéré R -hard.$L_2$$L_1$$L_2$$R$

Exemple simple

Supposons que nous voulions montrer que KNAPSACK est NP-difficile. Heureusement, nous savons que SUBSET-SUM est NP-complet, et il s’agit bien d’un cas particulier de KNAPSACK. La réduction

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

suffit; est l'instance KNAPSACK qui demande si nous pouvons obtenir au moins la valeur v avec des valeurs d'élément dans V de sorte que les poids correspondants provenant de W restent au-dessous de w au total. Nous n’avons pas besoin des restrictions de poids pour simuler SUBSET-SUM, nous les définissons simplement à des valeurs tautologiques.$(V,W,v,w)$$v$$V$$W$$w$

Problème d'exercice simple

Considérons le problème de MAX-3SAT: étant donné une formule propositionnelle et un entier k , déterminez s’il existe une interprétation de φ qui remplit au moins k clauses. Montrer que c'est NP-difficile.$\varphi$$k$$\varphi$$k$

3SAT est un cas particulier; avec m, le nombre de clauses de φ suffit.$f(\varphi) = (\varphi, m)$$m$$\varphi$

Exemple

Supposons que nous étudions le problème de SUBSET-SUM et que nous voulions montrer qu'il est NP-difficile.

Nous avons de la chance et savons que le problème de PARTITION est NP-complet. Nous confirmons qu’il s’agit bien d’un cas particulier de SUBSET-SUM et formulons

$\qquad \displaystyle f(A) = \begin{cases} \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\ \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else} \end{cases}$

où est l'ensemble d'entrée de PARTITION et est une instance de SUBSET-SUM qui demande après un sous-ensemble de sommant à . Ici, nous devons nous occuper du cas où il n’y a pas de approprié ; dans ce cas, nous donnons un exemple infaisable et arbitraire.( A , k ) A k $A$$(A,k)$$A$$k$$k$

Problème d'exercice

Considérez le problème LONGEST-PATH: à partir d’un graphe orienté , des nœuds de et d’un entier , déterminez s’il existe un chemin simple allant de à dans de longueur au moins .s , t G k s t G $G$$s,t$$G$$k$$s$$t$$G$$k$

Montrer que LONGEST-PATH est NP-hard.

HAMILTON-CYCLE est un problème NP-complet bien connu et un cas particulier de LONGEST-PATH; pour le nœud arbitraire dans suffit. Notez en particulier que la réduction de HAMILTON-PATH nécessite plus de travail.v $f(G) = (G,v,v,n)$$v$$G$

Tirer parti d'un problème connu à proximité

Face à un problème difficile, il est souvent judicieux d'essayer de rechercher un problème similaire qui a déjà fait ses preuves. Ou peut-être pouvez-vous immédiatement constater qu'un problème ressemble beaucoup à un problème connu.

Exemple de problème

Considérer un problème

nous souhaitons montrer que complet. Nous constatons rapidement qu’il est très proche d’un problème que nous savons déjà difficile, à savoir le problème de satisfiabilité (SAT) .$\mathsf{NP}$

L'adhésion à est simple à montrer. Le certificat est deux affectations. Clairement, on peut vérifier en temps polynomial si les assignations satisfont à une formule.$\mathsf{NP}$

dureté N P résulte d'une réduction de SAT . Étant donné une formule φ , nous la modifions en introduisant une nouvelle variable v . Nous ajoutons une nouvelle clause ( v ∨ ¬ v ) à la formule. Maintenant, si φ est satisfiable, il le sera avec v = ⊥ et v = ⊤ . Par conséquent, φ a au moins 2 assignations satisfaisantes. Par contre, si φ n'est pas satisfiable, il ne le deviendra certainement pas quelle que soit la valeur de v .$\mathsf{NP}$$\text{SAT}$$\varphi$$v$$(v \vee \neg v)$$\varphi$$v = \perp$$v = \top$$\varphi$$\varphi$$v$

Il s'ensuit que est N P- complet, c'est ce que nous voulions montrer.$\text{DOUBLE-SAT}$$\mathsf{NP}$

Trouver des problèmes à proximité

Réduire les problèmes est un genre d’art. L’expérience et l’ingéniosité sont souvent nécessaires. Heureusement, de nombreux problèmes difficiles sont déjà connus . Informatique et Intractabilité de Garey et Johnson: Un guide de la théorie de la NP-Complétude est un classique avec son annexe énumérant de nombreux problèmes. Google Scholar est aussi un ami.

En calculabilité, nous étudions souvent des ensembles de machines de Turing. En d'autres termes, nos objets sont des fonctions et nous avons accès à une numérotation de Gödel . C'est formidable car nous pouvons faire à peu près ce que nous voulons avec la fonction d'entrée, tant que nous restons calculables.

Supposons que nous voulions montrer que n'est pas décidable. Notre objectif est d’atteindre l’équivalence de Doom$L$

$\qquad \langle M \rangle \in K \iff \langle f_M \rangle \in L$

avec le problème de l' arrêt (ou toute autre langue indécidable / problème).$K = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ halts} \}$

Nous devons donc trouver une cartographie computable¹ de telle sorte que f M est toujours calculable. C'est un acte créatif éclairé par l'équivalence du destin. Voir quelques exemples pour avoir une idée de comment cela fonctionne:$\langle M \rangle \mapsto \langle f_M \rangle$$f_M$

• Cartographie des réductions à compléter de $A_{\mathrm{TM}}$
• Est-il possible de mapper réduire l'une de ces langues à l'autre?

$L$$\overline{K}$

• La régularité de la langue acceptée par une machine de Turing donnée est-elle une propriété semi-décidable?
• L'ensemble des fonctions constantes calculables est-il récursivement énumérable?

1. C'est là qu'intervient la numérotation de Gödel: nous obtenons la calculabilité de cette cartographie (généralement) gratuitement.

$A$$B$$B$$A$

Une stratégie utile consiste à travailler à partir de grandes compilations de problèmes de la classe de complexité en question et à trouver les "problèmes les plus proches apparents" au problème à l'étude. Computers and Intractability, un guide de la théorie de l’exhaustivité des NP, Garey et Johnson, est une excellente référence dans ce domaine. Il est organisé en différents types de problèmes.