La réduction de Karp est-elle identique à la réduction de Levin

12

Définition: réduction de Karp

Un langage est Karp réductible à un langage B s'il existe une fonction calculable en temps polynomial f : { 0 , 1 } { 0 , 1 } telle que pour chaque x , x A si et seulement si f ( x ) B .ABf:{0,1}{0,1}xxAf(x)B

Définition: réduction de Levin

Un problème de recherche est Levin réductible à un problème de recherche V B s'il existe une fonction temporelle polynomiale f que Karp réduit L ( V A ) à L ( V B ) et qu'il existe des fonctions calculables en temps polynomial g et h telles queVAVBfL(VA)L(VB)gh

  1. ,x,yVAf(x),g(x,y)VB

  2. f(x),zVBx,h(x,z)VA

Ces réductions sont-elles équivalentes?


Je pense que les deux définitions sont équivalentes. Pour toutes deux langues A et B , si A est réductible Karp à B , alors A est Levin réductibles à B .NPABABAB

Voici ma preuve:

Soit et ¯ x être des instances arbitraires de A tout x ' soit celle de B . Supposons que V A et V B sont des vérificateurs de A et B . Soit y et ¯ y avoir des certificats arbitraires de x et ¯ x selon V A . Soit z soit celle de x ' en fonction de V B .xx¯AxBVAVBAByy¯xx¯VAzxVB

Construire de nouveaux vérificateurs et V B avec de nouveaux certificats y et z :VAVByz

VA(x,y):

  1. : si f ( x ) f ( ¯ x ) , rejeter. Sinon, sortir V A ( ¯ x , ¯ y ) .y=0,x¯,y¯f(x)f(x¯)VA(x¯,y¯)
  2. : sortie V B ( f ( x ) , z ) .y=1,zVB(f(x),z)

VB(x,z):

  1. : sortie V B ( x ' , z ) .z=0,zVB(x,z)

  2. : Si x 'f ( x ) , rejeter. Sinon, sortir V A ( x , y ) .z=1,x,yxf(x)VA(x,y)

Les fonctions calculables polynomiales en temps et h sont définies comme suit:gh

g(x,y)

  1. : Sortie1 , ¯ x , ¯ y .y=0,x¯,y¯1,x¯,y¯

  2. : Sortie0 , z .y=1,z0,z

h(x,z)

  1. : Sortie1 , z .z=0,z1,z

  2. : Sortie0 , x , y .z=1,x,y0,x,y

Soit l'ensemble de tous les certificats de x selon V A et Z x ' l'ensemble de tous les certificats de x ' en fonction de V B . Alors l'ensemble de tous les certificats de x selon V A est 0 ¯ x Y ¯ x + 1 Z f ( x ) tel que f ( x ) = f ( ¯ x )YxxVAZxxVBxVA0x¯Yx¯+1Zf(x)f(x)=f(x¯), et l'ensemble de tous les certificats de selon V B est 0 Z x + 1 ¯ x Y ¯ x tels que x = f ( ¯ x ) .xVB0Zx+1x¯Yx¯x=f(x¯)

(Ceci est dérivé du langage d'acceptation de et V B. )VAVB

Soit maintenant , la partie restante est facile à vérifier.x=f(x)

cc
la source
Avant de prouver votre affirmation, vous devez définir ce que signifie une langue étant Levin réductible à une autre.
Tsuyoshi Ito

Réponses:

14

Non. Tout d'abord, notez que la réduction Levin n'a de sens que pour les classes dont le certificat a une signification, par exemple alors que la réduction Karp est générale. Le mot «certificat» pour un problème n'a de sens que lorsqu'un vérificateur est fixé. La réduction de Levin suppose que les vérificateurs sont fixes. Vous ne pouvez pas modifier les vérificateurs. (Dans ce qui suit, je suppose que les vérificateurs de certificats sont fixés comme requis par la définition de la réduction Levin.)NP

Deuxièmement, la réduction de Levin signifie que l'on peut trouver le certificat pour l'un à partir du certificat pour l'autre. Il est vrai que les réductions bien connues de Karp entre les problèmes naturels se révèlent être la réduction de Levin mais cela n'a pas besoin d'être vrai en général.

Si nous pouvons réduire les instances d'un problème au problème B, cela ne signifie pas que nous avons un moyen de calculer un certificat pour l'un à partir d'un certificat pour l'autre.AB

Pour que cela soit vrai, nous avons besoin du fait qu'un problème de recherche de certificat correspondant au problème de décision est un temps polynomial réductible au problème de décision. Cela est vrai pour les problèmes mais n'est pas connu comme étant généralement vrai même pour les problèmes N P.NP-completeNP

Kaveh
la source
Je suis d'accord sur votre premier point selon lequel la réduction de Karp est plus générale que la réduction de Karp. Selon lui, je pense que mon problème devrait être modifié comme "Soit et L 2 deux langues en N P. Si L 1 est Karp réductible en L 2 , alors L 1 est Levin réductible en L 2. " Cependant, je ne suis pas d'accord sur vos autres commentaires. L1L2NPL1L2L1L2
cc
Dans ma preuve, laissons d'abord et L 2 arbitraires dans ces deux langages. Puisqu'ils sont en N P , il y a P TM M 1 et M 2 . Pour chaque instance x L 1 , l'ensemble de tous les certificats est Y x pour T M 1 . De même, nous définissons Z x pour x L 2 . Puisque L 1 est Karp réductible en L 2 , il y a une telle fL1L2NPM1M2xL1YxTM1ZxxL2L1L2fcomme défini.
cc
Maintenant, nous avons construit de nouveaux et M 2 . Pour chaque instance x L 1 , le nouvel ensemble de tous les certificats est 0 Y x + 1 Z f ( x ) , tandis que pour chaque instance f ( x ) L 2 , le nouvel ensemble de tous les certificats est 0 Z f ( x ) + 1 x Y x . (Ici, nous utilisons des expressions régulières) Ce sont des certificats légaux et tous lesM1M2xL10Yx+1Zf(x)f(x)L20Zf(x)+1xYx et M 2 . Soit dit en passant, il existe P fonctions g et h, telles que définies, qui transforment tous les certificats possibles d'un problème à l'autre. M1M2gh
cc
ps: On n'a pas besoin de donner une transformation de où il n'y a pas x L 1 tel que x ' = f ( x ) , étant donné que les réductions Karp et Levin sont tous les deux beaucoup à un mappage. Je pense que cela peut répondre à l'avant-dernier paragraphe. xL2xL1x=f(x)
cc
@cc, il semble que vous pensez toujours que vous pouvez changer les vérificateurs, vous ne pouvez pas, la définition de la réduction de Levin est pour les problèmes de recherche, c'est-à-dire que les vérificateurs sont fixes.
Kaveh
5

x1,x2L1f(x1)=f(x2)L2wx1x2

M1(x1,0,w)=M1(x1,w)=1

M1(x2,0,w)=M1(x2,w)=0

g(x1,0,w)=1,x1,w

f(x1)=f(x2)M2(f(x2),1,x1,w))=M1(x1,w)=11,x1,wf(x2) mais

h(f(x2),1,x1,w)=0,wx2

Vor
la source
Merci beaucoup d'avoir signalé le contre-exemple. J'ai modifié la construction et je pense que cela fonctionne maintenant. Pourriez-vous, s'il vous plaît, y jeter un œil?
cc