Jenis pengurangan dan definisi kekerasan yang terkait

15

Misalkan A direduksi ke B, yaitu, . Oleh karena itu, mesin Turing menerima A memiliki akses ke oracle untuk B . Biarkan Turing mesin menerima A menjadi M A dan oracle untuk B menjadi O B . Jenis pengurangan:ABABAMABOB

  • Turing pengurangan: dapat membuat beberapa pertanyaan untuk O B .MAOB

  • Reduksi karp: Juga disebut "polinomial time Turing reduction": Input ke harus dibuat dalam polytime. Selain itu, jumlah kueri ke O B harus dibatasi oleh polinomial. Dalam hal ini: P A = P B .OBOBPA=PB

  • Banyak-satu pengurangan Turing: dapat membuat hanya satu query untuk O B , selama nya langkah terakhir. Karenanya respons oracle tidak dapat dimodifikasi. Namun, waktu yang dibutuhkan untuk dibangun input ke O B tidak perlu dibatasi oleh polinomial. Setara: ( m menunjukkan banyak-satu reduksi)MAOBOBm

    jika fungsi yang dapat dihitung f : Σ Σ sedemikian rupa sehingga f ( x ) BAmBf:ΣΣ .f(x)BxA

  • Pengurangan masak: Juga disebut "pengurangan waktu banyak-satu polinomial": Pengurangan banyak-banyak di mana waktu yang digunakan untuk membangun input ke harus dibatasi oleh polinomial. Setara: ( p m yang menunjukkan banyak-satu reduksi)OBmp

    jika sebuahpoli-waktufungsi dihitung f : Σ *Σ * sehingga f ( x ) BAmpBf:ΣΣ .f(x)BxA

  • Pengurangan pelit: Juga disebut "waktu polinomial satu-satu pengurangan": pengurangan A Masak di mana setiap contoh dari dipetakan ke contoh yang unik dari B . Setara: ( p 1 yang menunjukkan reduksi pelit)AB1p

    jika sebuahpoli-waktudihitung bijection f : Σ *Σ * sehingga f ( x ) BA1pBf:ΣΣ .f(x)BxA

    Pengurangan ini mempertahankan sejumlah solusi. Oleh karena itu .#MA=#OB

Kita dapat mendefinisikan lebih banyak jenis reduksi dengan membatasi jumlah permintaan oracle, tetapi mengabaikannya, bisakah seseorang memberi tahu saya jika saya mendapatkan nomenklatur untuk berbagai jenis reduksi yang digunakan, dengan benar. Apakah masalah NP-lengkap didefinisikan dengan hormat pengurangan Cook atau pengurangan pelit? Adakah yang bisa dengan ramah memberikan contoh masalah yang NP-lengkap di bawah Cook dan tidak dalam pengurangan pelit.

Jika saya tidak salah, kelas # P-Complete didefinisikan sehubungan dengan pengurangan Karp.

Pavithran Iyer
sumber

Jawaban:

7

Definisi Anda tentang pengurangan pelit tidak benar. Anda bingung dengan pengurangan satu kali satu polinomial yang merupakan kasus khusus pengurangan Karp. Mereka tidak mempertahankan jumlah "solusi". Silakan lihat jawaban ini untuk lebih lanjut tentang pengurangan mengingat jumlah sertifikat.

Selebihnya tampak baik meskipun biasanya lebih baik untuk melihatnya dalam grafik dua dimensi:

  • kompleksitas reduksi: komputasi, waktu polinomial, ruang logaritmik, dll.
  • jenis akses: Turing, banyak-satu, satu-satu, dll.

Apakah masalah NP-lengkap didefinisikan dengan hormat pengurangan Cook atau pengurangan pelit?

kekerasan dan kelengkapan didefinisikan wrt pengurangan Karp (polytime banyak-satu), tidak Masak atau pengurangan pelit.NP

Adakah yang bisa dengan ramah memberikan contoh masalah yang NP-lengkap di bawah Cook dan tidak dalam pengurangan pelit.

Ambil komplemen dari SAT, itu adalah lengkap untuk di bawah pengurangan Cook, tidak diyakini lengkap untuk N P di bawah pengurangan Karp. Pengurangan karp termasuk pengurangan polytime satu-satu.NPNP

kelas # P-Complete didefinisikan sehubungan dengan pengurangan Karp

#P

Kaveh
sumber
Maaf, sepertinya saya telah menukar terminologi "Pengurangan Karp" dan "Pengurangan Cook". Jika saya menukar, maka itu cocok dengan tanggapan Anda. Terima kasih. Mengenai pengurangan pelit, apakah Anda mengatakan bahwa mereka tidak mempertahankan jumlah "solusi"? Jika demikian, saya lihat dalam Teorema 17.10 dari Arora & Barak (Halaman 299) bahwa reduksi pelit memang mempertahankan sejumlah solusi. Referensi lain: ( cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf )
Pavithran Iyer
Di sini dikatakan pengurangan pelit dari L ke SAT, memetakan setiap instance x dari L ke instance unik SAT (yaitu, peta reduksi adalah satu-satu): [ cse.cuhk.edu.hk/~andrejb/csc5170/notes /10L10.pdf] . Bukankah benar untuk berasumsi bahwa jika jumlah solusi dipertahankan oleh reduksi, maka peta itu adalah satu-satu?
Pavithran Iyer
@Pavithran, apa yang Anda tulis dalam pertanyaan Anda bukanlah definisi dari pengurangan pelit. Untuk jawabannya, lihat latihan 2.13 di buku mereka.
Kaveh
0

Definisi pengurangan Karp tidak benar. Pengurangan Karp adalah pengurangan Turing polinomial-waktu di mana oracleHAIB disebut tepat sekali, selama pengurangan langkah terakhir.

Björn Lindqvist
sumber
Secara khusus, definisi pengurangan Cook dan Karp telah diaktifkan.
David Richerby