Czy redukcja karp jest identyczna z redukcją Levina

Definicja: Redukcja karp

Język jest karpem redukowalnym do języka jeśli istnieje funkcja obliczalna w czasie wielomianowym tak, że dla każdego , wtedy i tylko wtedy, .$A$$B$$f:\{0,1\}^*\rightarrow\{0,1\}^*$$x$$x\in A$$f(x)\in B$

Definicja: Redukcja Levina

Problem wyszukiwania można sprowadzić do Levina do problemu wyszukiwania jeśli istnieje funkcja czasu wielomianowego której Karp redukuje do a istnieją funkcje obliczeniowe wielomianowe i takie, że$V_A$$V_B$$f$$L(V_A)$$L(V_B)$$g$$h$

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

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

Czy te redukcje są równoważne?

Myślę, że dwie definicje są równoważne. Dla dwóch języków$\mathsf{NP}$$A$ i$B$ , jeżelijest Karp zredukować do B , a następniejest Levin zredukować do B .$A$$B$$A$$B$

Oto mój dowód:

Niech i ¯ x być dowolne instancje A gdy x ' być, że z B . Załóżmy V i V B są weryfikatorzy z A i B . Niech Y i Ż Y być dowolne certyfikaty x i Ż x w zależności od V A . Niech z będzie, że od X " zgodnie z V B .$x$$\overline{x}$$A$$x'$$B$$V_A$$V_B$$A$$B$$y$$\overline{y}$$x$$\overline{x}$$V_A$$z$$x'$$V_B$

Skonstruować nowe weryfikatorów and V " B o nowe certyfikaty, Y ' i Z ' :$V'_A$$V'_B$$y'$$z'$

$V'_A(x,y'):$

1. : jeśli f ( x ) ≠ f ( Ż x ) , odrzucenia. W przeciwnym razie wyprowadzić V A ( ¯ x , ¯ y ) .$y'=\langle 0,\overline{x},\overline{y}\rangle$$f(x)\ne f(\overline{x})$$V_A(\overline{x},\overline{y})$
2. : Wyjście V B ( F ( x ) , z ) .$y'=\langle 1,z\rangle$$V_B(f(x),z)$

$V'_B(x',z'):$

1. : Wyjście V B ( x ' , oo ) .$z'=\langle 0,z\rangle$$V_B(x',z)$

2. : jeśli x ' ≠ f ( x ) , odrzucenia. W przeciwnym razie wyprowadzić V A ( x , y ) .$z'=\langle 1,x,y\rangle$$x'\ne f(x)$$V_A(x,y)$

Funkcje obliczane w czasie wielomianowym i h są zdefiniowane jak poniżej:$g$$h$

$g(x,y')$

1. : Wyjście ⟨ 1 , Ż x , Ż Y ⟩ .$y'=\langle 0,\overline{x},\overline{y}\rangle$$\langle 1,\overline{x},\overline{y}\rangle$

2. : Wyjście ⟨ 0 , oo ⟩ .$y'=\langle 1,z\rangle$$\langle 0,z\rangle$

$h(x',z')$

1. : Wyjście ⟨ 1 , z ⟩ .$z'=\langle 0,z\rangle$$\langle 1,z\rangle$

2. : Wyjście ⟨ 0 , x , y ⟩ .$z'=\langle 1,x,y\rangle$$\langle 0,x,y\rangle$

Niech oznacza zbiór wszystkich certyfikatów X według V A , a Z x " oznacza zbiór wszystkich certyfikatów X ' zgodnie V B . Zatem zestaw wszystkich certyfikatów x według V ′ A wynosi 0 ¯ x Y ¯ x + 1 Z f ( x ) tak, że f ( x ) = f ( ¯ x$Y_x$$x$$V_A$$Z_{x'}$$x'$$V_B$$x$$V'_A$$0\overline{x}Y_\overline{x}+1Z_{f(x)}$$f(x)=f(\overline{x})$, a zestaw wszystkich certyfikatów zgodnie z V ′ B wynosi 0 Z x ′ + 1 ¯ x Y ¯ x, tak że x ′ = f ( ¯ x ) .$x'$$V'_B$$0Z_{x'}+1\overline{x}Y_\overline{x}$$x'=f(\overline{x})$

(Pochodzi z języka akceptującego i V ′ B. )$V'_A$$V'_B$

Teraz niech , reszta jest łatwa do sprawdzenia.$x'=f(x)$

Nie. Pierwsza uwaga, że ​​redukcja Levina ma sens tylko w odniesieniu do klas, które certyfikat ma znaczenie, np. podczas gdy redukcja Karp jest ogólna. Słowo „certyfikat” dla problemu ma sens tylko wtedy, gdy weryfikator jest naprawiony. Redukcja Levina zakłada, że ​​weryfikatory są naprawione. Nie możesz zmienić weryfikatorów. (Poniżej zakładam, że weryfikatory certyfikatów są ustalone zgodnie z definicją redukcji Levina).$\mathsf{NP}$

Po drugie, redukcja Levina oznacza, że ​​można znaleźć certyfikat dla jednego z certyfikatu dla drugiego. Prawdą jest, że dobrze znanymi redukcjami karpów między problemami naturalnymi okazują się redukcje Levina, ale nie musi to być prawda w ogóle.

Jeśli możemy zredukować przypadki problemu do problemu B , nie oznacza to, że mamy sposób na obliczenie certyfikatu dla jednego z certyfikatu dla drugiego.$A$$B$

Aby było to prawdą, potrzebujemy faktu, że problem wyszukiwania certyfikatu odpowiadający problemowi decyzyjnemu jest czasem wielomianowym redukującym się do problemu decyzyjnego. Jest to prawdziwe w odniesieniu do problemów, ale nie wiadomo, że ogólnie prawdą nawet N P problemów.$\mathsf{NP\text{-}complete}$$\mathsf{NP}$

Szybkie kontrprzykład dla dowodu: załóżmy, że , f ( x 1 ) = f ( x 2 ) ∈ L 2 , oraz w to ważny certyfikat dla x 1 , ale nie dla x $x_1, x_2 \in L_1$$f(x_1) = f(x_2) \in L_2$$w$$x_1$$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$

Z definicji $g(x_1,\langle 0,w \rangle) = \langle 1,x_1,w \rangle$

tak, M ' 2 ( f ( x 2 ) , ⟨ 1 , x 1 , w ⟩ ) ) = K 1 ( x 1 , w ) = 1 to ⟨ 1 , x 1 , w ⟩ jest ważny certyfikat f ( x 2$f(x_1)=f(x_2)$$M'_2(f(x_2),\langle 1,x_1, w \rangle)) = M_1(x_1,w) = 1$$\langle 1,x_1, w \rangle$$f(x_2)$ ale

która nie jest ważny certyfikat x $h(f(x_2), \langle 1,x_1, w \rangle) = \langle 0, w \rangle$$x_2$