Est-Karp Réduction identique à Levin réduction

Question

Définition: Karp Réduction

Une langue $ A $ est réductibles Karp à une langue $ B $ s'il y a un temps polynôme fonction calculable $ f: \ {0,1 \} ^ * \ rightarrow \ {0,1 \} ^ * $ de telle sorte que pour chaque $ x $, $ x \ in A $ si et seulement si $ f (x) \ in B $.

Définition: Levin Réduction

Un problème de recherche $ V_A $ est Levin réductibles à un problème de recherche $ V_B $ s'il est fonction polynomiale $ f $ qui Karp réduit $ L (V_A) $ à $ L (V_B) $ et il y a polynomial fonctions calculables $ g $ et $ h $ tel que

1. $ \ langle x, y \ rangle \ in V_A \ implique \ langle f (x), g (x, y) \ rangle \ in V_B $,

2. $ \ langle f (x), z \ rangle \ in V_B \ implique \ langle x, h (x, z) \ rangle \ in V_A $

sont ces réductions équivalentes?

---

Je pense que les deux définitions sont équivalentes. Pour tout deux $ \ mathsf {NP} $ langues $ A $ et $ B $, si $ A $ est réductible à Karp $ B $, alors $ A $ est Levin réductibles à $ B $.

Voici ma preuve:

Soit $ x $ et $ \ overline {x} $ des cas arbitraires de $ A $, tandis que $ x '$ soit celui de $ B $. $ $ V_A On suppose et $ V_B $ sont de $ A vérificateurs $ et $ B $. Soit $ y $ et $ \ overline {y} $ soit des certificats arbitraires de $ x $ et $ \ overline {x} $ selon $ V_A $. Soit $ z $ soit celui de $ x '$ selon $ V_B $.

Construction de nouvelles $ V'_A $ vérificateurs et $ V'_B $ avec de nouveaux certificats $ y '$ et $ z' $:

$ V'_A (x, y): $

1. $ y '= \ langle 0, \ overline {x}, \ overline {y} \ rangle $: Si $ f (x) \ ne f (\ overline {x}) $, rejeter. Sinon sortie $ V_A (\ overline {x}, \ overline {y}) $.
2. $ y '= \ langle 1, z \ rangle $:. V_B sortie de $ (f (x), z) $

V'_B $ (X 'z'): $

1. $ z '= \ langle 0, z \ rangle $: $ V_B sortie (x'., Z) $

2. $ z '= \ langle 1, x, y \ rangle $: Si $ x' \ ne f (x) $, rejeter. Sinon, la sortie de V_A $ (x, y) $.

Le temps polynomiale fonctions calculables $ g $ et $ h $ sont définis comme suit:

$ g (x, y ') $

1. $ y '= \ langle 0, \ overline {x}, \ overline {y} \ rangle $: sortie $ \ langle 1, \ overline {x}, \ overline {y} \ rangle $.

2. $ y '= \ langle 1, z \ rangle $:. Output $ \ langle 0, z \ rangle $

$ h (x 'z') $

1. $ z '= \ langle 0, z \ rangle $:. Output $ \ langle 1, z \ rangle $

2. $ z '= \ langle 1, x, y \ rangle $:. Output $ \ langle 0, x, y \ rangle $

Soit $ Y_x $ l'ensemble de tous les certificats de $ x $ $ selon V_A $ et $ Z_ {x '} $ l'ensemble de tous les certificats de $ x' $ selon $ V_B $. Ensuite, l'ensemble de tous les certificats de $ x $ $ selon V'_A $ 0 $ \ overline {x} Y_ \ overline {x} + {1Z_ f (x)} $ tel que $ f (x) = f (\ overline {x}) $, et l'ensemble de tous les certificats de $ x '$ selon $ $ V'_B est 0Z_ $ {x'} + 1 \ overline {x} Y_ \ overline {x} $ tel que $ x '= f (\ overline { x}) $.

(Ceci est dérivé de la langue d'accepter de $ V'_A $ et $ V'_B $).

Soit $ x '= f (x) $, la partie reste est facile à vérifier.

Answer 1

Non

. Notons d'abord que la réduction Levin n'a de sens que par rapport aux classes qui le certificat a un sens, par exemple $ \ Mathsf {NP} $, tandis que la réduction Karp est générale. Le mot « certificat » pour un problème est logique que lorsqu'un vérificateur est fixé. La réduction de Levin suppose que les vérificateurs sont fixés. Vous ne pouvez pas changer les vérificateurs. (Dans ce qui suit, je suppose que des certificats sont vérificateurs fixés conformément à la définition de la réduction Levin.)

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

Si nous pouvons réduire les cas d'un problème $ A $ à un problème $ B $ cela ne signifie pas que nous avons une façon de calculer un certificat pour un certificat d'un pour l'autre.

Pour que cela soit vrai que nous devons le fait qu'il ya un problème de recherche de certificat correspondant au problème de décision est réductibles polynomiale au problème de la décision. Cela est vrai pour $ \ mathsf {NP de texte {-}} complet. $ Problèmes, mais ne sait pas être vrai en général, même pour $ \ mathsf {NP} $ Problèmes

Answer 2

Un contre rapide pour votre preuve: supposons que x 1 $, x 2 \ dans L_1 $, $ f (x 1) = f (x 2) \ dans L_2 $, et $ w $ est un certificat valide pour x 1 $ $, mais pour $ x 2 $

M_1' $ (x 1, \ langle 0, w \ rangle) = M_1 (x 1, w) = 1 $

M_1' $ (x 2, \ langle 0, w \ rangle) = M_1 (x 2, w) = 0 $

Par définition $ g (x 1, \ langle 0, w \ rangle) = \ langle 1, x 1, w \ rangle $

$ f (x 1) = f (x 2) de sorte $ M'_2 $ (f (x 2), \ langle 1, x 1, w \ rangle)) = M_1 (x 1, w) = 1 si $ $ \ langle 1, x 1, w \ rangle $ est un certificat valide pour $ f (x 2) $, mais

$ h (f (x 2), \ langle 1, x 1, w \ rangle) = \ langle 0, w \ rangle $ qui ne soit pas un certificat valide pour $ x 2 $