Pengurangan dari buku.

Ini sepanjang garis " Algoritma dari Kitab ". Meskipun reduksi adalah algoritme juga, saya pikir ragu bahwa orang akan memikirkan pengurangan respons terhadap pertanyaan tentang algoritme dari buku ini. Oleh karena itu permintaan yang terpisah!

Pengurangan dari semua jenis dipersilahkan.

Saya akan mulai dengan pengurangan yang sangat sederhana dari vertex cover ke multicut pada bintang. Pengurangan hampir menunjukkan sendiri begitu masalah sumber diidentifikasi (sebelum itu saya akan merasa sulit untuk percaya bahwa masalah akan sulit pada bintang-bintang). Pengurangan ini melibatkan membangun bintang dengan daun, dan menghubungkan sepasang terminal dengan setiap sisi dalam grafik, dan "mudah dilihat" bahwa ia bekerja. Saya akan memperbarui ini dengan tautan ke referensi, setelah saya menemukannya.$n$

Mereka yang kehilangan konteks buku mungkin ingin melihat pertanyaan tentang Algoritma dari buku ini .

Pembaruan: Saya menyadari bahwa saya tidak sepenuhnya jelas tentang apa yang memenuhi syarat sebagai pengurangan dari buku ini. Saya menemukan masalah ini sedikit rumit, jadi saya mengaku setengah sengaja menghindari masalah dengan menyelipkan referensi ke utas lainnya :)

Jadi izinkan saya menggambarkan apa yang ada dalam pikiran saya, dan saya kira tidak usah dikatakan lagi - YMMV dalam hal ini. Saya bermaksud analogi langsung dengan maksud asli Bukti dari Buku. Saya telah melihat pengurangan yang sangat pintar, dan membuat saya ternganga melihat bagaimana urutan pemikiran itu terjadi pada siapa pun. Sementara pengurangan seperti itu membuat saya kagum, itu bukan contoh yang saya ingin kumpulkan dalam konteks ini.

Apa yang saya cari adalah reduksi yang digambarkan tanpa terlalu banyak kesulitan, dan mungkin sedikit mengejutkan, karena mereka mudah dipahami tetapi tidak mudah dibuat. Jika Anda memperkirakan bahwa pengurangan pertanyaan akan membutuhkan kuliah untuk dibahas, maka kemungkinan itu tidak sesuai dengan tagihan, meskipun saya yakin mungkin ada pengecualian di mana ide tingkat tinggi anggun dan iblis ada di rinciannya (untuk catatan, saya tidak yakin bisa memikirkan apa pun).

Contoh yang saya berikan adalah sengaja sederhana, dan semoga sedikit - jika tidak sempurna - menggambarkan karakteristik ini. Pertama kali saya mendengar tentang multi-cut adalah di ruang kelas, dan instruktur kami mulai dengan mengatakan bahwa tidak hanya NP-keras secara umum, tetapi juga NP-hard ketika terbatas pada pohon ... {dramatis jeda} ketinggian satu . Saya ingat tidak bisa membuktikannya dengan segera, meskipun tampaknya jelas dalam retrospeksi.

Saya kira jelas dalam retrospeksi erat menggambarkan apa yang saya cari. Saya tidak yakin apakah ini ada hubungannya dengan kerumitan deskripsi - mungkin ada situasi di mana sesuatu yang kelihatannya suram dapat dikategorikan elegan - merasa bebas untuk memberikan contoh Anda (pengecualian?), Tapi saya akan sangat menghargai pembenaran. Mengingat bahwa setelah beberapa titik ini adalah masalah selera, Anda tentu harus merasa bebas untuk menemukan apa yang saya lihat sangat rumit, sangat cantik. Saya menantikan untuk melihat berbagai contoh!

Rabin menunjukkan satu arah (x ^ 2 mod N = pq) tanpa faktorisasi N dengan reduksi yang menunjukkan bahwa jika Anda dapat mengambil modul akar kuadrat N = pq maka Anda dapat memfaktorkan N.

Dalam pembelajaran mesin, ada banyak pengurangan yang menarik. Berikut ini beberapa contohnya:

• klasifikasi multikelas ke klasifikasi biner ( tautan ) - seseorang dapat memecahkan masalah memilih di antara banyak kelas dengan memecahkan masalah yang lebih mudah dalam memilih antara dua.
• pembelajaran yang kuat hingga pembelajaran yang lemah ( boosting ) - seseorang dapat mencapai tingkat kesalahan yang rendah secara sewenang-wenang mengingat kemampuan untuk mencapai sedikit lebih baik daripada acak.
• peringkat ke klasifikasi ( tautan )
• kuadrat kehilangan klasifikasi ( probing ) - seseorang dapat memperkirakan probabilitas keanggotaan kelas dengan menggunakan classifier dengan tingkat kesalahan kecil.

Sebuah tutorial oleh Alina Beygelzimer, John Langford, dan Bianca Zadrozny mencakup beberapa orang lain.

Cook-Levin Theorem

Setiap masalah dalam NP dapat dikurangi dalam polytime oleh mesin turing deterministik ke SAT. Untuk referensi lihat 1 .

Penggandaan integer untuk transformasi Fourier yang cepat!

Teorema Rice

Salah satu favoritku. Ini mengurangi masalah penghentian untuk setiap set indeks (atau komplemennya). Lihat, misalnya, Sipser, masalah 5.28.

SAT ke 3SAT

$k$$k \gt 3$

3SAT hingga 3COL

Menggunakan gadget untuk mengurangi 3SAT menjadi masalah dalam memutuskan apakah grafik dapat diwarnai dengan 3 warna. Untuk referensi lihat 1 .

Dalam arti mengatakan - oh itu sederhana - dalam retrospeksi:

mengurangi penyortiran ke masalah cembung lambung.

SAMBUTAN SAMPAI DENGAN 3-SETS ke SUMBER SUMBER

$U=\{1,2,\ldots,3m\}$$S_1,\ldots,S_n$$U$$m$$U$

$w_1,\ldots,w_n$$K$$K$

Pikirkan himpunan sebagai vektor dalam { 0 , 1 } 3 m , dan anggap vektor ini sebagai bilangan bulat di basis n + 1 , sehingga S i menjadi w i = $S_i$$\{0,1\}^{3m}$$n+1$$S_i$$w_i=\sum_{j\in S_i} (n+1)^{3m-j}$$K=\sum_{j=0}^{3m-1} (n+1)^j$

(Sumber saya adalah buku Papadimitriou.)