Apakah Pengurangan Karp identik dengan Pengurangan Levin

Definisi: Pengurangan Karp

Bahasa adalah Karp dapat direduksi menjadi bahasa jika ada fungsi yang dapat dihitung polinomial waktu sedemikian rupa sehingga untuk setiap , jika dan hanya jika . $A$ $B$ $f:\{0,1\}^*\rightarrow\{0,1\}^*$ $x$ $x\in A$ $f(x)\in B$

Definisi: Pengurangan Levin

Masalah pencarian adalah Levin dapat direduksi menjadi masalah pencarian jika ada fungsi waktu polinom sehingga Karp mengurangi menjadi dan ada fungsi yang dihitung waktu polinomial dan sedemikian rupa sehingga $V_A$ $V_B$ $f$ $L(V_A)$ $L(V_B)$ $g$ $h$

$\langle x, y \rangle \in V_A \implies \langle f(x), g(x,y) \rangle \in V_B$ ,
$\langle f(x), z \rangle \in V_B \implies \langle x, h(x,z) \rangle \in V_A$

Apakah pengurangan ini setara?

Saya pikir kedua definisi itu setara. Untuk setiap dua bahasa dan , jika adalah Karp direduksi ke , maka adalah Levin direduksi ke . $\mathsf{NP}$ $A$ $B$ $A$ $B$ $A$ $B$

Ini buktiku:

Biarkan dan menjadi contoh sewenang-wenang dari sementara bahwa dari . Misalkan dan adalah pengukur dari dan . Biarkan dan menjadi sertifikat dan - menurut . Biarkan menjadi milik menurut . $x$ $\overline{x}$ $A$ $x'$ $B$ $V_A$ $V_B$ $A$ $B$ $y$ $\overline{y}$ $x$ $\overline{x}$ $V_A$ $z$ $x'$ $V_B$

Bangun verifier baru dan dengan sertifikat baru dan : $V'_A$ $V'_B$ $y'$ $z'$

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

$y'=\langle 0,\overline{x},\overline{y}\rangle$ : Jika , tolak. Jika tidak, . $f(x)\ne f(\overline{x})$ $V_A(\overline{x},\overline{y})$
$y'=\langle 1,z\rangle$ : Output . $V_B(f(x),z)$

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

$z'=\langle 0,z\rangle$ : Output . $V_B(x',z)$
$z'=\langle 1,x,y\rangle$ : Jika , tolak. Kalau tidak, output . $x'\ne f(x)$ $V_A(x,y)$

Fungsi komputasi polinomial-waktu dan didefinisikan sebagai berikut: $g$ $h$

$g(x,y')$

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

$h(x',z')$

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

Biarkan menjadi himpunan semua sertifikat menurut dan menjadi himpunan semua sertifikat sesuai dengan . Maka himpunan semua sertifikat menurut adalah sedemikian rupa sehingga , dan himpunan semua sertifikat menurut adalah sedemikian rupa sehingga . $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})$ $x'$ $V'_B$ $0Z_{x'}+1\overline{x}Y_\overline{x}$ $x'=f(\overline{x})$

(Ini berasal dari bahasa penerima dan .) $V'_A$ $V'_B$

Sekarang biarkan , bagian sisanya mudah untuk diperiksa. $x'=f(x)$

Sebelum membuktikan klaim Anda, Anda harus mendefinisikan apa artinya dengan bahasa yang dapat direduksi oleh Levin ke bahasa lain.

Tsuyoshi Ito

Jawaban:

Tidak. Catatan pertama bahwa pengurangan Levin hanya masuk akal sehubungan dengan kelas yang sertifikat memiliki arti, misalnya sementara pengurangan Karp bersifat umum. Kata "sertifikat" untuk masalah masuk akal hanya ketika verifier diperbaiki. Pengurangan Levin mengasumsikan bahwa verifier sudah diperbaiki. Anda tidak dapat mengubah penguji. (Berikut ini saya berasumsi bahwa pengesah sertifikat diperbaiki seperti yang dipersyaratkan oleh definisi pengurangan Levin.) $\mathsf{NP}$

Kedua, pengurangan Levin berarti bahwa seseorang dapat menemukan sertifikat untuk satu dari sertifikat yang lain. Memang benar bahwa pengurangan Karp yang terkenal antara masalah-masalah alam berubah menjadi pengurangan Levin tetapi ini tidak perlu benar secara umum.

Jika kita dapat mengurangi contoh masalah menjadi masalah itu tidak berarti kita memiliki cara menghitung sertifikat untuk satu dari satu sertifikat untuk yang lainnya. $A$ $B$

Agar ini benar, kita perlu fakta bahwa masalah pencarian sertifikat yang sesuai dengan masalah keputusan adalah waktu polinomial yang dapat direduksi menjadi masalah keputusan. Ini berlaku untuk masalah tetapi tidak diketahui benar secara umum bahkan untuk masalah . $\mathsf{NP\text{-}complete}$ $\mathsf{NP}$

Kaveh
sumber

Saya setuju pada poin pertama Anda bahwa pengurangan Karp lebih umum daripada pengurangan Karp. Menurutnya, saya pikir masalah saya harus diubah sebagai "Biarkan dan menjadi dua bahasa dalam . Jika adalah Karp dapat direduksi menjadi , maka adalah Levin dapat direduksi menjadi ." Namun, saya tidak setuju dengan komentar Anda yang lain.

L_{1}

$L_1$

L_{2}

$L_2$

N P

$NP$

L_{1}

$L_1$

L_{2}

$L_2$

L_{1}

$L_1$

L_{2}

$L_2$

Dalam buktiku, pertama-tama biarkan dan menjadi dua bahasa yang arbitrer. Karena mereka berada di , ada P TM dan . Untuk setiap instance , set semua sertifikat adalah untuk . Demikian pula, kami mendefinisikan untuk . Karena adalah Karp dapat direduksi menjadi , ada seperti yang didefinisikan.

L_{1}

$L_1$

L_{2}

$L_2$

N P

$NP$

M_{1}

$M_1$

M_{2}

$M_2$

x \in L_{1}

$x\in L_1$

Y_{x}

$Y_x$

T M_{1}

$TM_1$

Z_{x^{'}}

$Z_{x'}$

x^{'} \in L_{2}

$x'\in L_2$

L_{1}

$L_1$

L_{2}

$L_2$

f

$f$

Sekarang, kami membuat dan . Untuk setiap instance , set baru semua sertifikat adalah , sedangkan untuk setiap instance , set baru semua sertifikat adalah . (Di sini kami menggunakan ekspresi reguler) Ini adalah legal dan semua sertifikat untuk dan . By the way, ada fungsi P dan seperti yang didefinisikan mengubah semua sertifikat yang mungkin dari satu masalah ke yang lain.

M_{1}^{'}

$M_1'$

M_{2}^{'}

$M_2'$

x \in L_{1}

$x\in L_1$

0 Y_{x} + 1 Z_{f (x)}

$0Y_x+1Z_{f(x)}$

f (x) \in L_{2}

$f(x)\in L_2$

0 Z_{f (x)} + 1 x Y_{x}

$0Z_{f(x)}+1xY_x$

M_{1}^{'}

$M_1'$

M_{2}^{'}

$M_2'$

g

$g$

h

$h$

ps: Kita tidak perlu memberikan transformasi dari mana tidak ada sehingga , karena pengurangan Karp dan Levin keduanya banyak menjadi satu pemetaan. Saya pikir ini bisa menjawab paragraf terakhir yang kedua.

x^{'} \in L_{2}

$x'\in L_2$

x \in L_{1}

$x\in L_1$

x^{'} = f (x)

$x'=f(x)$

@ cc, tampaknya Anda masih berpikir bahwa Anda dapat mengubah verifier, Anda tidak bisa, definisi pengurangan Levin adalah untuk masalah pencarian, yaitu verifier diperbaiki.

Kaveh

Contoh tandingan cepat untuk bukti Anda: misalkan , , dan adalah sertifikat yang valid untuk tetapi tidak untuk $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$

Menurut definisi $g(x_1,\langle 0,w \rangle) = \langle 1,x_1,w \rangle$

$f(x_1)=f(x_2)$ jadi jadi adalah sertifikat yang valid untuk tetapi $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)$

$h(f(x_2), \langle 1,x_1, w \rangle) = \langle 0, w \rangle$ yang bukan sertifikat yang valid untuk $x_2$

Vor
sumber

Terima kasih banyak telah menunjukkan sampel tandingan. Saya telah memodifikasi konstruksinya dan saya pikir itu berhasil sekarang. Bisakah Anda melihatnya?