Apakah Pengurangan Karp identik dengan Pengurangan Levin

12

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 .ABf:{0,1}{0,1}xxAf(x)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 sehinggaVAVBfL(VA)L(VB)gh

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

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

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 . A B A B A BNPABABAB

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 A x B V A V B A B y ¯ y x ¯ x V A z x V Bxx¯AxBVAVBAByy¯xx¯VAzxVB

Bangun verifier baru dan dengan sertifikat baru dan : V B y z VAVByz

VA(x,y):

  1. f ( x ) f ( ¯ x ) V A ( ¯ x , ¯ y )y=0,x¯,y¯ : Jika , tolak. Jika tidak, .f(x)f(x¯)VA(x¯,y¯)
  2. V B ( f ( x ) , z )y=1,z : Output .VB(f(x),z)

VB(x,z):

  1. V B ( x ' , z )z=0,z : Output .VB(x,z)

  2. x 'f ( x ) V A ( x , y )z=1,x,y : Jika , tolak. Kalau tidak, output .xf(x)VA(x,y)

Fungsi komputasi polinomial-waktu dan didefinisikan sebagai berikut:hgh

g(x,y)

  1. 1 , ¯ x , ¯ yy=0,x¯,y¯ : Output .1,x¯,y¯

  2. 0 , z y=1,z : Output .0,z

h(x,z)

  1. 1 , z z=0,z : Output .1,z

  2. 0 , x , y z=1,x,y : Output .0,x,y

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 . x V A Z x x V B x V A 0 ¯ x Y ¯ x + 1 Z f ( x ) f ( x ) = f ( ¯ x ) x V B 0 Z x + 1 ¯ x Y ¯ x x = f ( ¯YxxVAZxxVBxVA0x¯Yx¯+1Zf(x)f(x)=f(x¯)xVB0Zx+1x¯Yx¯x=f(x¯)

(Ini berasal dari bahasa penerima dan .) V BVAVB

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

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

Jawaban:

14

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.)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.BAB

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 .N PNP-completeNP

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 2 N P L 1 L 2 L 1 L 2L1L2NPL1L2L1L2
cc
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 2 N P M 1 M 2 x L 1 Y x T M 1 Z x x L 2 L 1 L 2 fL1L2NPM1M2xL1YxTM1ZxxL2L1L2f
cc
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 2 x L 1 0 Y x + 1 Z f ( x ) f ( x ) L 2 0 Z f ( x ) + 1 x Y x M 1 M 2 g hM1M2xL10Yx+1Zf(x)f(x)L20Zf(x)+1xYxM1M2gh
cc
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 L 1 x = f ( x )xL2xL1x=f(x)
cc
@ cc, tampaknya Anda masih berpikir bahwa Anda dapat mengubah verifier, Anda tidak bisa, definisi pengurangan Levin adalah untuk masalah pencarian, yaitu verifier diperbaiki.
Kaveh
5

Contoh tandingan cepat untuk bukti Anda: misalkan , , dan adalah sertifikat yang valid untuk tetapi tidak untukx1,x2L1f(x1)=f(x2)L2wx1x2

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

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

Menurut definisig(x1,0,w)=1,x1,w

f(x1)=f(x2) jadi jadi adalah sertifikat yang valid untuk tetapiM2(f(x2),1,x1,w))=M1(x1,w)=11,x1,wf(x2)

x 2h(f(x2),1,x1,w)=0,w yang bukan sertifikat yang valid untukx2

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