Apa teknik umum untuk mengurangi masalah satu sama lain?

40

Dalam teori komputasi dan kompleksitas (dan mungkin bidang lainnya), reduksi ada di mana-mana. Ada banyak jenis, tetapi prinsipnya tetap sama: menunjukkan bahwa satu masalah setidaknya sekeras beberapa masalah lainnya dengan memetakan contoh dari ke yang setara dengan solusi di . Pada dasarnya, kami menunjukkan bahwa setiap solver untuk juga dapat menyelesaikan jika kami mengizinkannya menggunakan fungsi reduksi sebagai preprosesor.L1L2L2L1L1L2

Saya telah melakukan bagian pengurangan selama bertahun-tahun, dan sesuatu terus menggangguku. Sementara setiap pengurangan baru membutuhkan (lebih atau kurang) konstruksi kreatif, tugas itu bisa terasa berulang. Apakah ada kumpulan metode kanonik?

Apa saja teknik, pola, dan trik yang dapat digunakan secara berkala untuk membangun fungsi reduksi?

Ini seharusnya menjadi pertanyaan referensi . Oleh karena itu, harap berhati-hati untuk memberikan jawaban umum, yang disajikan secara didaktis yang diilustrasikan oleh setidaknya satu contoh tetapi tetap mencakup banyak situasi. Terima kasih!

Raphael
sumber
Lihat di sini untuk beberapa pemikiran tentang menemukan mitra dan ide yang cocok untuk pengurangan.
Raphael

Jawaban:

18

Kasus Khusus

Asumsikan kita ingin menunjukkan sehubungan dengan beberapa gagasan tentang pengurangan . Jika L_1 adalah kasus khusus dari L_2 , yang cukup sepele: kita pada dasarnya dapat menggunakan fungsi identitas. Intuisi di balik ini jelas: kasus umum setidaknya sekeras kasus khusus.L1RL2RL1L2

Dalam "latihan", kami diberikan dan terjebak dengan masalah memilih mitra reduksi yang baik , yaitu menemukan kasus khusus yang telah terbukti -hard.L 1 L 2 RL2L1L2R

Contoh sederhana

Asumsikan kita ingin menunjukkan bahwa KNAPSACK adalah NP-hard. Untungnya, kita tahu bahwa SUBSET-SUM adalah NP-complete, dan ini memang merupakan kasus khusus KNAPSACK. Pengurangan

f(A,k)=(A,(1,,1),k,|A|)

cukup; adalah instance KNAPSACK yang menanyakan apakah kita dapat mencapai setidaknya nilai dengan nilai item di sehingga bobot yang sesuai dari tetap di bawah total . Kami tidak memerlukan batasan berat untuk mensimulasikan SUBSET-SUM, jadi kami hanya mengaturnya ke nilai tautologis.v V W w(V,W,v,w)vVWw

Masalah olahraga sederhana

Pertimbangkan masalah MAX-3SAT: diberi rumus proposisional dan integer , putuskan apakah ada interpretasi yang memenuhi setidaknya klausa. Tunjukkan bahwa NP-hard.kφkkφk

3SAT adalah kasus khusus; dengan jumlah klausa dalam mencukupi.m φf(φ)=(φ,m)mφ

Contoh

Asumsikan kita sedang menyelidiki masalah SUBSET-SUM dan ingin menunjukkan bahwa itu NP-hard.

Kami beruntung dan tahu bahwa masalah PARTISI adalah NP-complete. Kami mengonfirmasikan bahwa ini memang kasus khusus SUBSET-SUM dan dirumuskan

f(A)={(A,12aAa),aAamod2=0(A,1+aA|a|),else

di mana adalah himpunan input PARTISI, dan adalah sebuah instance untuk SUBSET-SUM yang menanyakan setelah subset dari penjumlahan ke . Di sini, kita harus mengurus kasus bahwa tidak ada yang cocok ; dalam hal ini, kami memberikan contoh tidak layak yang sewenang-wenang.( A , k ) A k kA(A,k)Akk

Masalah Latihan

Pertimbangkan masalah LONGEST-PATH: diberi grafik diarahkan , node dari dan integer , putuskan apakah ada jalur sederhana dari ke di dengan panjang setidaknya .s , t G k s tGs,tGkstGk

Tunjukkan bahwa LAMA-PATH adalah NP-keras.

HAMILTON-CYCLE adalah masalah NP-complete yang terkenal dan kasus khusus LONGEST-PATH; untuk sembarang simpul dalam cukup. Perhatikan khususnya bagaimana pengurangan dari HAMILTON-PATH membutuhkan lebih banyak pekerjaan.v Gf(G)=(G,v,v,n)vG

Raphael
sumber
2
Berikut adalah contoh yang disebut masalah pembeli bepergian (TPP) yang memiliki banyak masalah sulit sebagai kasus khusus.
Juho
Contoh lain dari kemampuan komputasi adalah masalah penghentian khusus (yang biasanya terbukti secara langsung tidak dapat dipastikan), kasus khusus masalah penghentian umum.
Raphael
Apakah KNAPSACK benar-benar pengurangan yang benar dari SUBSET-SUM? KNAPSACK meminta nilai dan SUBSET-SUM meminta nilai yang tepat, bukan? Misalnya instance SUBSET-SUM akan menjadi instance 'tidak' (saya tidak bisa mendapatkan 4 dari hanya satu item dengan nilai 5), tetapi pengurangan KNAPSACK Anda akan mengurangi itu menjadi dan , jadi itu akan menjadi contoh 'ya' di sana ... Atau apakah saya kehilangan sesuatu? { 5 } , 4 { 5 } , { 1 } , 4 , 1 5 > 4>=v{5},4{5},{1},4,15>4
johnny
15

Memanfaatkan masalah terdekat yang diketahui

Ketika dihadapkan dengan masalah yang terasa sulit, sering kali merupakan ide yang baik untuk mencoba mencari masalah serupa yang sudah terbukti sulit. Atau, mungkin Anda dapat langsung melihat bahwa masalah sangat mirip dengan masalah yang diketahui.

Contoh masalah

Pertimbangkan suatu masalah

DOUBLE-SAT={φφ is a boolean formula with at least 2 satisfying assignments }

yang ingin kami tampilkan adalah -complete. Kami dengan cepat mencatat bahwa itu sangat dekat dengan masalah yang sudah kita tahu sulit, yaitu masalah kepuasan (SAT) .NP

Keanggotaan untuk mudah untuk ditampilkan. Sertifikatnya adalah dua tugas. Jelas, itu dapat diperiksa dalam waktu polinomial apakah tugas memenuhi formula.NP

SAT φ v ( v ¬ v ) φ v = v = φ φNP -kekuatan mengikuti dari pengurangan dari . Diberikan rumus , kami memodifikasinya dengan memperkenalkan variabel baru . Kami menambahkan klausa baru ke rumus. Sekarang, jika memuaskan, itu akan memuaskan dengan dan . Karenanya, memiliki setidaknya 2 tugas yang memuaskan. Di sisi lain, jika tidak memuaskan, itu pasti tidak akan memuaskan terlepas dari nilai .SATφv(v¬v)φv=⊥v=φφv

Maka adalah -complete, yang ingin kami perlihatkan.N PDOUBLE-SATNP

Menemukan masalah terdekat

Mengurangi masalah adalah semacam seni, dan pengalaman serta kecerdasan sering dibutuhkan. Untungnya, banyak masalah sulit sudah diketahui . Komputer dan Ketertarikan Garey dan Johnson: Panduan untuk Teori NP-Completeness adalah buku klasik dengan apendiksnya yang memuat banyak masalah. Google Cendekia juga seorang teman.

Juho
sumber
6

Dalam komputasi, kami sering menyelidiki set mesin Turing. Yaitu, objek kami adalah fungsi dan kami memiliki akses ke penomoran Gödel . Itu hebat karena kita dapat melakukan hampir semua yang kita inginkan dengan fungsi input, selama kita tetap dapat dihitung.

Asumsikan kita ingin menunjukkan bahwa tidak dapat memutuskan. Tujuan kami adalah mencapai kesetaraan azabL

MKfML

dengan masalah penghentian (atau bahasa / masalah lain yang tidak dapat dipastikan).K={MM(M) halts}

Maka, kita perlu membuat pemetaan computable¹ pemetaan sehingga selalu dapat dihitung. Ini adalah tindakan kreatif yang diinformasikan oleh kesetaraan azab. Lihat beberapa contoh untuk mendapatkan ide tentang cara kerjanya:f MMfMfM

Pekerjaan yang sama untuk menunjukkan bahwa tidak semi-decidable dengan memilih bahasa yang tidak semi-decidable sebagai mitra reduksi, misalnya :¯ KLK¯


  1. Di sinilah penomoran Gödel masuk: kami mendapatkan kompabilitas dari pemetaan ini (biasanya) secara gratis.
Raphael
sumber
-2

itu tergantung pada kelas kompleksitas yang terlibat, dan apakah seseorang ingin mengurangi dari diberikan ke tidak diketahui , atau tidak diketahui menjadi diberikan . skenario yang umum adalah untuk membuktikan masalah NP Hard atau NP Complete. teknik umum adalah membuat "gadget" di satu domain yang berperilaku dengan cara tertentu, meniru perilaku domain lain. misalnya untuk mengonversi SAT ke penutup titik, seseorang membuat "gadget" di penutup titik yang berperilaku mirip dengan klausa SAT, misalnya dalam peragaan slide berikut: NP Pengurangan lengkap oleh Krishnamoorthy (juga dengan contoh untuk jalur Hamilton).B B AABBA

strategi yang berguna adalah bekerja dari kompilasi besar masalah dari kelas kompleksitas yang dimaksud dan menemukan "masalah terdekat yang nyata" hingga masalah yang dipelajari. referensi yang sangat baik di sepanjang baris ini adalah Komputer dan Intractability, panduan untuk teori kelengkapan NP, Garey dan Johnson diorganisir oleh berbagai jenis masalah.

vzn
sumber
2
Saya ingin tahu apakah Anda memperhatikan catatan kaki dalam pertanyaan itu. Saya pikir jawabannya harus lebih spesifik dan menunjukkan bagaimana metode spesifik diterapkan. Ini sepertinya agak kabur dan umum. Sebagai peningkatan, bagaimana jika Anda menunjukkan bagaimana gadget dapat dibangun dan digunakan?
Juho
2
ABBA
powerpoint menunjukkan dua contoh gadget yang digunakan. contoh masalah terdekat: misalkan seseorang memiliki masalah terkait dengan teori bilangan. ada bagian G&J yang terkait dengan teori bilangan. dan sebagainya. adapun kelas kompleksitas lain di luar NP, ada banyak, tetapi daftar masalahnya tidak selengkap atau mudah diperoleh. jadi dengan kata lain untuk mempersempit pertanyaan awal mungkin harus dibatasi untuk pengurangan lengkap NP ...?
vzn
2
Saya sarankan menambahkan semua informasi ke jawabannya, karena komentar mungkin dihapus kapan saja. Tautan ke slide mungkin putus besok juga. Apa yang saya maksudkan dengan masalah terdekat: apa yang harus saya lakukan tepat ketika saya menemukan masalah yang terlihat serupa (anggap saya seorang pemula total)?
Juho