Motivation de l'utilisation des réductions de Karp dans la théorie de la complétude de

La notion de réductions de temps polynomiales (réductions Cook) est l'abstraction d'un concept très intuitif: résoudre efficacement un problème en utilisant un algorithme pour un problème différent.

Cependant, dans la théorie de la complétude de , la notion de dureté de N P est capturée par des réductions de cartographie (réductions de Karp). Ce concept de réductions "restreintes" est beaucoup moins intuitif (du moins pour moi). Il semble même un peu artificiel, car il crée une notion de dureté un peu moins intuitive; par ce que je fais référence au fait que N P ne contient pas trivialement c o - N P . Bien que dans la théorie de la complexité, nous sommes très habitués au concept selon lequel être capable de résoudre un problème tel que S A T n'implique pas que nous pouvons résoudre ¯ S A $\mathcal{NP}$$\mathcal{NP}$$\mathcal{NP}$$co-\mathcal{NP}$$\mathsf{SAT}$$\overline{\mathsf{SAT}}$, dans les paramètres naturels (qui sont capturés par les réductions de Cook), en supposant que nous avons un algorithme pour résoudre , nous pouvons résoudre ¯ S A T simplement en exécutant l'algorithme pour S A T et en retournant le contraire.$\mathsf{SAT}$$\overline{\mathsf{SAT}}$$\mathsf{SAT}$

Ma question est pourquoi devrions-nous utiliser les réductions de Karp pour la théorie de la complétude de ? Quelle notion intuitive capture-t-elle? Comment est-ce lié à la façon dont nous comprenons la «dureté du calcul» dans le monde réel?$\mathcal{NP}$

Comme les réductions de Turing, plusieurs réductions sont entrées dans la théorie de la complexité à partir de la littérature sur la théorie de la calculabilité / récursivité. Les réductions Cook et Karp sont des versions théoriques de la complexité naturelle des réductions existantes similaires de calculabilité.

Il existe une manière intuitive d'expliquer plusieurs réductions: c'est une restriction des réductions de Turing où nous ne pouvons poser qu'une seule question à l'oracle et la réponse de l'oracle sera notre réponse.

Maintenant, la question est pourquoi devrions-nous étudier cela (et tout autre type de réductions comme la table de vérité, la table de vérité faible, etc.)?

Ces réductions donnent une image plus précise que les réductions de Turing. Les réductions de Turing sont trop puissantes pour faire la distinction entre de nombreux concepts. Une très grande partie de la théorie de la calculabilité est consacrée à l'étude des diplômes ce / re. La notion d'un ensemble de ce est centrale. Nous pouvons avoir une machine TM qui peut énumérer un ensemble infini, nous ne pourrons peut-être pas énumérer son complément. Si vous souhaitez étudier les ensembles de ce, la réduction de Turing est trop forte car les ensembles de ce ne sont pas fermés en dessous. Tant de réductions sont un moyen (et peut-être le) naturel de définir des réductions à cette fin.

D'autres types de réductions sont définis pour des raisons similaires. Si vous êtes intéressé, je vous suggère de vérifier la "Théorie de la récursion classique" de Piergiorgio Odifreddi. Il contient un chapitre assez complet sur les différentes réductions et leurs relations.

Maintenant, pour la théorie de la complexité, l'argument est similaire. Si vous acceptez que est une classe de problèmes extrêmement naturelle et que vous souhaitez étudier N P , les réductions de cuisson sont trop fortes. Le choix naturel est une réduction plus faible telle que N P est fermé en dessous et nous pouvons prouver l'existence d'un problème complet par rapport à cette réduction pour $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

il y a plusieurs questions sur ce site concernant les réductions Cook vs Karp. n'ont pas vu une description très claire de cela pour le néophyte parce que c'est quelque peu intrinsèquement subtil à bien des égards et c'est un domaine de recherche actif / ouvert. voici quelques références qui peuvent être utiles pour y remédier. comme le résume wikipedia, "les réductions de plusieurs sont utiles car la plupart des classes de complexité bien étudiées sont fermées sous un certain type de réductibilité de plusieurs, y compris P, NP, L, NL, co-NP, PSPACE, EXP et bien d'autres. Cependant, ces classes ne sont pas fermées par des réductions arbitraires de plusieurs. "

il semble juste de dire que même les théoriciens avancés réfléchissent activement à la distinction et aux différences exactes comme dans les références ci-dessous et l'histoire complète ne sera pas disponible à moins que d'importantes séparations de classes de complexité ouverte ne soient résolues, c'est-à-dire que ces questions semblent se situer au centre de la vs connue inconnue.

[1] Cook contre Karp-Levin: Séparer les notions d'exhaustivité si NP n'est pas petit (1992) Lutz, Mayordomo

[2] Cook et Karp sont-ils toujours les mêmes? Beigel et Fortnow

[3] Plus de problèmes NP-Complete (PPT) voir les diapositives 9-14 sur l'historique et les distinctions de réduction Cook vs Karp