Peut-on construire une réduction de Karp à partir d'une réduction de Cook entre des problèmes NP?

Nous avons eu plusieurs questions sur la relation entre les réductions Cook et Karp . Il est clair que les réductions de Cook (réductions de Turing à temps polynomial) ne définissent pas la même notion de complétude NP que les réductions de Karp (réductions de plusieurs à un temps polynomial), qui sont généralement utilisées. En particulier, les réductions Cook ne peuvent pas séparer NP de co-NP même si P NP. Nous ne devons donc pas utiliser les réductions Cook dans les preuves de réduction typiques.$\neq$

Maintenant, les étudiants ont trouvé un travail évalué par les pairs [1] qui utilise une réduction Cook pour montrer qu'un problème est NP-difficile. Je ne leur ai pas donné la note complète pour la réduction qu'ils ont prise à partir de là, mais je me demande.

Étant donné que les réductions de Cook font définir une notion similaire de dureté que les réductions Karp, je pense qu'ils devraient être en mesure de séparer P de NPC resp. co-NPC, en supposant P NP. En particulier, (quelque chose comme), ce qui suit devrait être vrai:$\neq$

.$\qquad\displaystyle L_1 \in \mathrm{NP}, L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1 \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$

La pépite importante est que l' insensibilité ainsi mentionnée ci-dessus est contournée. On "sait" maintenant - par définition de NPC - que L 2 ≤ K a r p L 1 .$L_1 \in \mathrm{NP}$$L_2 \leq_{\mathrm{Karp}} L_1$

Comme l'a noté Vor , ce n'est pas si simple (notation adaptée):

$L_1 \in \mathrm{NPC}_{\mathrm{Cook}}$$L_2 \in \mathrm{NPC}_{\mathrm{Karp}} \subseteq \mathrm{NP}$$L_2 \leq_{\mathrm{Cook}} L_1$$L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$$\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}}$

Il peut y avoir d'autres différences entre les deux PNJ mais co-NP.

$P$

$\qquad\displaystyle L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1, P(L_1,L_2) \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$

1. Sur la complexité de l'alignement de séquences multiples par L. Wang et T. Jiang (1994)

C'est un problème TCS généralement ouvert soumis à des recherches en cours sur la question de savoir si les conditions exactes des réductions Cook & Karp sont équivalentes et est apparemment étroitement liée à la question ouverte NP =? coNP et à d'autres séparations de classes de complexité, par exemple E =? NE (wrt sparse languages).

voici deux articles de recherche sur le sujet et d'autres pistes sur tcs.se via une question similaire:

• Cook et Karp sont-ils toujours les mêmes? Beigel, Fortnow

• Cook vs Karp-Levin: séparer les notions d'exhaustivité si le NP n'est pas petit (1995) Lutz, Mayordomo

• plusieurs réductions vs réductions de Turing pour définir le PNJ , tcs.se

En général, pour transformer mécaniquement un problème Cook-complete en un problème Karp-complete, il doit y avoir quelque chose de spécial avec la langue elle-même.

$L$

$L$

$x$$x'=f(x)$$L(x)\neq L(x')$

$g(x)$$f(g(x))$

Comme vous pouvez le voir, ces propriétés ne sont normalement pas vues dans la théorie de la complexité, la théorie de la calculabilité. En conclusion, il est extrêmement peu probable de pouvoir transformer Cook en Karp.