Existe-t-il une telle notion de "réductions de calcul efficacement" ou serait-ce non utile

Question

La plupart des réductions des preuves de la dureté NP que j'ai rencontrées sont efficaces dans le sens qui donnent une instance de notre problème dur, elles donnent un algorithme de temps polynomial pour notre problème en utilisant des réductions. Toutes les réductions de 21 problèmes classiques considérés par R. Karp fonctionnent de cette façon. Un exemple très simple peut être une réduction de manière indépendante_set à la clique, vient de construire le graphe de complément de votre entrée.

Mais lorsque vous envisagez la preuve du célèbre Theorem Cook-Levin Ce SAT est rempli de NP, la réduction commence d'un TM non déterministe et d'un polynôme, qui existe par définition. Mais pour moi, il n'est pas clair comment obtenir ce polynôme efficacement, ce qui signifie que je sais un TM non déterministe à partir de laquelle je sais qu'il court en temps polynomial, il n'est pas clair comment calculer ce polynôme et je soupçonne fortement qu'il n'est pas calculable à tous.

SO Soley à partir du codage des problèmes de NP-Terminal par la classe de TMS de temps polynomial non déterministe (le polynôme lui-même n'est pas codé aussi loin que je sache) Je ne vois aucun moyen de donner une réduction de manière efficace, La preuve susmentionnée montre simplement qu'il existe certains, mais pas comment l'obtenir.

Peut-être j'ai peut-être compris quelque chose de mal, mais j'ai l'impression que les réductions étant-ce que les réductions sont plus fortes en ce sens qu'ils sont effectivement calculables, c'est-à-dire un problème que nous pouvons calculer notre réduction et ne pas simplement connaître son existence.

Cela a-t-il déjà été noté? Et si oui, existe-t-il une telle notion comme une "réduction efficace calculable" ou serait-elle peu pratique de limiter les réductions pour être calculables? Pour moi, d'une perspective plus pratique, et aussi la façon dont je vois parfois des réductions introduites ("comme si nous avons un algorithme pour convertir une instance à une autre") Il serait hautement souhaitable de savoir comment obtenir cet algorithme / réduction, alors réellement Il semble plus naturel de la demander, mais pourquoi n'est-ce pas fait?

Answer 1

belle question! Je pense que votre notion d'une "réduction efficace calculable" est intéressante et d'être étudiée, mais pas aussi fondamentale que des réductions standard. Permettez-moi de fournir des observations sur cette notion qui peut être éclairante:

Observation 1: Il n'a aucun sens de parler de réductions de manière efficace d'une langue à une autre; seulement d'une famille de langues à une autre.

En particulier, vous semblez être mélangé lorsque vous écrivez ceci:

La plupart des réductions des preuves de la dureté NP que j'ai rencontrées sont efficaces dans le sens qui donnent une instance de notre problème dur, elles donnent un algorithme de temps polynomial pour notre problème en utilisant des réductions. Toutes les réductions des 21 problèmes classiques considérés par R. Karp fonctionnent de cette façon.

Une réduction de, disons, Vertexcover à 3SAT est une machine de Turing $ f $ qui transforme les instances de vertexcover dans des instances de 3SAT. Comme il s'agit d'une machine de Turing, elle est efficacement calculable par définition. Il n'est donc pas surprenant que toutes les réductions que vous avez vues de cette forme sont efficacement calculables.

En d'autres termes, si nous examinons simplement des réductions d'une langue à une autre, chaque réduction est efficacement calculable!

Ceci est différent du cas du théorème de cuisson-levin, où nous devons montrer une réduction $ f $ d'une langue np arbitraire au SAT. Ensuite, il pourrait être logique de déterminer si cette réduction - paramétrée par la langue dans NP - est efficace ou non. Mais cela nous amène à mon deuxième point:

Observation 2: Qu'est-ce qui compte comme une réduction efficacement dépend de la représentation des langues.

Ceci est important car les réductions standard (de nombreuses réductions de plusieurs à une ou des réductions de turing) ne dépendent pas de la manière dont la langue est représentée. Pour une réduction de $ l $ à $ l '$ , je considère $ l $ et $ l '$ pour être sous-ensembles de $ \ {0, 1 \ } ^ * $ . Mais pour votre notion de calculable efficacement pour avoir un sens, nous devons avoir accès à une représentation de $ l $ (nous ne le faisons probablement pas besoin d'une représentation de $ l '$ ).

Pour que ce point soit plus clair, envisagez la réduction de la preuve du théorème de cuisson-levin, que vous avez élevé. La preuve considère une langue $ l $ , représenté par une machine à trouble nondéterministe polynomiale $ N $ . Ensuite, il montre que $ l $ est réductible au SAT. Vous dites que cette réduction n'est pas de manière efficace, mais cela dépend de la manière dont $ n $ est représenté, c'est-à-dire la définition d'une machine de diurnure nondéterminée polynomial N $ N $ :

• Définition 1: Un NTM de polynôme-Time est une machine à trouble nondéterministe telle qu'il existe un polynôme $ p (n) $ , de sorte que la TM s'arrête toujours dans le temps au plus $ p (n) $ .

• Définition 2: Un NTM de temps polynomial est constitué d'une machine à trouble non déterministe, ainsi qu'un polynôme $ p (n) $ . La façon dont il fonctionne est que, sur n'importe quelle branche, il n'est exécuté que pour $ p (n) $ étapes; Si cela ne s'arrête pas à cette époque, cette branche est ignorée.

Cela peut sembler que je fais la définition 2 de la définition et que la définition n'est pas naturelle, mais les deux sont toutes deux des définitions parfaitement valides d'un NTM polynomial-temporel qui ont les deux mérites. Et pour la théorie classique de P, NP et NP-Complétude, ces deux définitions sont équivalentes. La bonne chose à propos de la définition 2 est qu'un NTM est autorisé à diverger sur certaines branches; Vous ne vous inquiétez pas à ce sujet, car la sémantique d'exécution dit que nous venons d'oublier cela une fois que le temps de fonctionnement passe au-dessus de $ p (n) $

.

.

Cependant, les définitions deviennent inéquicibles en matière de réductions de calcul efficace. Notez que, selon la définition 1, lorsque nous recevons une langue définie par une langue NTM $ N $ , nous n'avons aucune idée de son temps de fonctionnement, donc nous ne pouvons donc pas être capable de le réduire au SAT (plus sur ce ci-dessous). Mais selon la définition 2, une partie de la NTM $ N $ est qu'il est livré avec un polynôme, et nous connaissons donc son temps de fonctionnement. Par conséquent, nous pouvons réduire efficacement toutes les langues np à SAT si nous utilisons la définition 2.

En outre, nous n'avons que des machines à troubles non déterministes; Nous pourrions définir de manière équivalente NP en utilisant Verifie

machines Turing. Ensuite, la définition d'une réduction effectivement calculable pourrait être autre chose!

TL; DR: en fonction de la manière dont une langue dans NP est représentée, et en particulier en fonction de la définition d'un NTM polynomial-temporel, il peut être vrai ou faux que chaque langue dans NP est effectivement réductible au SAT. En d'autres termes, l'ensemble des réductions de calcul efficacement des modifications dépendant du modèle de calcul utilisé pour représenter des langues dans NP.

---

Maintenant à ce stade, des points donnés (1) et (2), une question reste toujours: la réduction du théorème du cupin-levin devrait-elle être efficace? En particulier, supposons que nous fixions les définitions suivantes:

• Les langues dans NP sont représentées par des machines de Turning non déterministes dont l'exécution est délimitée par un polynôme inconnu $ p $ (c.-à-d. Définition 1).

• donné une langue $ l $ , nous disons que la classe de langues np est efficacement de poly-time réductible à < SPAN CLASSE="MATH-CONTENEUR"> $ L $ Si ce qui suit contient: il y a une touche TM $ f $ qui prend comme entrée $ \ lambes n, w \ rangs $ , où $ n $ est un NTM polynomial NTM et $ w $ est une entrée sur $ n $ , tel que $ w \ in L (n) $ si et seulement si $ f (\ lger n, w \ rangle) \ in l $ . En outre, $ F $ doit exécuter en temps polynôme (dans son entrée $ \ langle n, w \ rangs $ ).

En d'autres termes, au point d'adressage (1), nous supposons que les langues dans NP sont représentées par des machines de Turning non déterministes sans une liaison polynomiale explicite. Et pour traiter le point 2), dans notre définition de réductible efficacement, nous parlons d'une réduction de la catégorie , dans ce cas, NP, à une seule langue. Maintenant, nous avons l'observation suivante:

Observation 3: (Cook-Levin n'est pas efficace) La classe NP n'est pas efficacement réductible au SAT.

Laissez-nous voir pourquoi cela est vrai. Supposons une contradiction qu'une réduction efficace $ f $ existe. L'idée est que nous essaierons de résoudre un problème difficile (dire, de temps doublement exponential) en prenant son instance, en le transformant en une NTM polynomial et demandant $ F $ pour le réduire au SAT. Donc, laissez $ l_ {dur} $ être un problème nécessitant une heure doublement exponentielle à résoudre (ceci existe par le théorème de la hiérarchie temporelle), et laissez $ m_ {dur} $ soit un (déterministe) tm qui le résout. Compte tenu de toute instance $ w $ du problème, définissez la classe NTM suivante $ n_w $ : \ commence {align *} N_w:= & \ Text {"Sur Toute entrée $ A $, première exécution} m_ {difficile} \\ & \ Text {sur entrée} w \ texte {. Quand il s'arrête, acceptez si} \\ & \ text {IT accepte et rejeter s'il rejette. "} \ fin {align *}

Maintenant, nous pouvons utiliser ceci pour résoudre $ l_ {dur} $ $ en temps exponentiel (pas double exponentiel), comme suit. En entrée $ w $ , nous construisons d'abord $ n_w $ , qui a une constante plus que < Span Classe="Conteneur mathématique"> $ w $ . Ensuite, nous passons $ \ lambes n_w, \ epsilon \ rangs $ (le deuxième argument, $ \ epsilon $ , est juste un espace réservé ici) à $ f $ pour le réduire au SAT. $ f $ nous donne une instance de SAT qui est à la taille de la taille polynomiale en $ n_w $ et $ f $ ne prend que du temps polynomial pour fonctionner. Donc, nous nous retrouvons avec une instance de satellite de taille polynomiale dans $ w $ ; Maintenant, nous le résolvons dans un délai exponentiel dans $ w $ à l'aide de la recherche de force brute.

---

Ce point (3) semble suggérer que la plupart du temps, aucune classe de langues intéressante ne sera réductible dans ce sens efficace pour une seule langue. Il sera simplement trop difficile, car vous pouvez exploiter ce calcul pour résoudre ensuite des problèmes difficiles en les codant dans le cadre d'une entrée TM à la réduction effective. Cependant, quelque chose est un peu louche ici, car si nous nourrissons la TMS $ N_W $ dans la réduction du théorme de cuisson-levin, nous finirions avec de très grandes formules SAT, exponentielle dans $ w $ . Donc, peut-être que notre définition doit être modifiée afin que $ f $ fonctionne de temps polynôme dans le heure de fonctionnement de "Math

-Container "> $ n_w $ , pas seulement polynôme dans l'entrée $ \ langle n_w, \ epsilon \ rangs $

.

.

Observation 4: Si nous permettons aux réductions de Turing (de nombreux à plusieurs), Cook-Levin peut être efficace.

comme D.W. dit dans un commentaire:

Je pense que l'on peut construire une réduction efficace de la cuisson, par doublage itératif. Cela aide-t-il?

Je crois aussi que c'est vrai. En particulier, nous pouvons changer notre définition d'une "réduction effective" du NP à une langue $ l $ en disant que la réduction ne renvoie pas simplement une instance de $ l $ , mais retourne de nombreuses instances de $ l $ en séquence et utilise un oracle pour $ l $ pour résoudre le problème initial. Ensuite, pour résoudre un problème général dans NP, vous pouvez essayer des polynômes plus gros et plus volumineux $ p $ jusqu'à ce que vous obtenez la bonne durée de fonctionnement. Vous pouvez détecter si un polynôme particulier limite la durée de fonctionnement de toutes les branches de la NTM par une réduction séparée du SAT.

Disclaimer

Je ne suis pas un expert dans ce sujet. Ce ne sont là que quelques notes préliminaires sur l'idée et je ne sais pas si quelqu'un l'a étudié dans la littérature.

P.s. Bien que cela ne soit peut-être pas directement lié, votre question sur l'envoi de réductions efficaces me rappelle une idée que j'avais eue, quant à la question de savoir si des langues sont à la norme P ou au NP, mais si elles sont pratiquées. Ceci est liée à l'idée de développer une théorie de la complexité efficace ou constructive. J'ai posé des questions et j'ai ensuite répondu à la question de définir des langues pratiquées et prativement np ici .