Haruskah reduksi membuat kita lebih atau kurang optimis untuk keterlacakan masalah?

Tampak bagi saya bahwa kebanyakan ahli teori kompleksitas umumnya percaya pada aturan filosofis berikut:

Jika kita tidak tahu algoritma yang efisien untuk masalah , dan kita dapat mengurangi masalah A ke masalah B , maka ada mungkin tidak algoritma yang efisien untuk masalah B , baik.$A$$A$$B$$B$

Inilah sebabnya mengapa, misalnya, ketika masalah baru terbukti NP-Complete kita hanya file itu pergi sebagai "terlalu keras" daripada mendapatkan bersemangat tentang pendekatan baru (masalah ) yang akhirnya mungkin menunjukkan P = N P .$B$$P = NP$

Saya sedang membahas ini dengan sesama mahasiswa pascasarjana di bidang ilmiah lain. Dia menemukan ide ini sangat berlawanan dengan intuisi. Analoginya:

Anda seorang penjelajah, mencari jembatan antara benua Amerika Utara dan Asia. Selama berbulan-bulan Anda telah mencoba dan gagal menemukan jembatan darat dari daratan Amerika Serikat ke Asia. Kemudian Anda menemukan bahwa daratan AS terhubung melalui darat ke wilayah Alaska. Anda menyadari bahwa jembatan darat dari Alaska ke Asia akan menyiratkan jembatan darat dari daratan AS ke Asia, yang Anda yakin tidak ada. Jadi, Anda tidak membuang waktu menjelajahi dekat Alaska; kamu pulang saja.

Aturan filosofis kami sebelumnya terdengar sangat konyol dalam konteks ini. Saya tidak bisa memikirkan bantahan yang bagus! Jadi saya menyerahkannya kepada kalian: Mengapa kita harus memperlakukan pengurangan sebagai masalah $A \to B$$B$ lebih sulit daripada membuat masalah lebih mudah?$A$

Saya pikir ini adalah pertanyaan yang sangat bagus. Untuk menjawabnya kita perlu menyadari bahwa:

• tidak semua pengurangan sama,
• untuk merasa optimis, kita perlu belajar sesuatu yang benar-benar bermanfaat.

Biasanya, setiap kali kami menemukan pengurangan nontrivial , itu jatuh dalam salah satu kategori berikut:$A \to B$

1. Kami mempelajari sesuatu yang bermanfaat tentang masalah A (dan tidak ada masalah tentang B).
2. Kami mempelajari sesuatu yang mengecilkan hati tentang masalah B (dan tidak ada tentang masalah A).

Sedikit lebih tepat, kedua kasus ini dapat dikarakterisasi sebagai berikut:

1. Kami menemukan bahwa masalah A memiliki beberapa struktur tersembunyi, yang memungkinkan untuk merancang algoritma baru dan pintar untuk menyelesaikan masalah A. Kami hanya perlu tahu cara menyelesaikan masalah B.

2. Kami menyadari bahwa dalam beberapa kasus khusus, masalah B pada dasarnya hanya masalah A yang menyamar. Kita sekarang dapat melihat bahwa algoritma apa pun untuk menyelesaikan masalah B harus menyelesaikan setidaknya kasus khusus ini dengan benar; dan menyelesaikan kasus-kasus khusus ini pada dasarnya sama dengan memecahkan masalah A. Kita kembali pada titik awal: untuk membuat kemajuan dengan masalah B, kita harus terlebih dahulu membuat beberapa kemajuan dengan masalah A.

Pengurangan tipe 1 adalah umum dalam konteks hasil positif, dan ini tentu saja merupakan alasan yang baik untuk merasa optimis.

Namun, jika Anda mempertimbangkan pengurangan kekerasan yang kami temui dalam konteks, misalnya, bukti kekerasan NP, mereka hampir selalu tipe 2.

Perhatikan bahwa meskipun Anda tidak tahu apa pun tentang kompleksitas komputasi masalah A atau masalah B, Anda tetap dapat mengetahui apakah pengurangan Anda adalah tipe 1 atau tipe 2. Oleh karena itu kami tidak perlu percaya, misalnya, P ≠ NP untuk tentukan apakah kita harus merasa optimis atau pesimis. Kita bisa melihat apa yang telah kita pelajari berkat pengurangannya.

Apa yang hilang dari analogi ini adalah beberapa gagasan tentang jarak relatif yang terlibat. Mari kita ganti Alaska dalam analogi kita dengan bulan:

Anda seorang penjelajah, mencari jembatan antara benua Amerika Utara dan Asia. Selama berbulan-bulan Anda telah mencoba dan gagal menemukan jembatan darat dari daratan Amerika Serikat ke Asia. Kemudian Anda menemukan bahwa daratan AS terhubung dengan daratan ke bulan. Anda sudah yakin bahwa bulan adalah jarak yang sangat jauh dari Asia, jadi Anda sekarang dapat yakin bahwa Amerika Utara juga sangat jauh dari Asia oleh ketidaksetaraan segitiga.

Tidak benar bahwa kita selalu melihat teorema reduksi sebagai pernyataan kekerasan. Sebagai contoh, dalam algoritma kita sering mengurangi masalah ke LP dan SDP untuk menyelesaikannya. Ini tidak ditafsirkan sebagai hasil kekerasan tetapi hasil algoritmik. Namun, meskipun secara teknis pengurangan, kami sering tidak merujuknya seperti itu. Yang kami maksud dengan reduksi biasanya adalah reduksi untuk beberapa (NP-) masalah sulit.

$A$$B$$A$$B$$B$$A$$A$$A$$B$$B$. Sebagian besar peneliti merasa lebih mungkin bahwa P tidak sama dengan NP, dan bahkan menduga bahwa SAT membutuhkan waktu eksponensial. Dengan kata lain SAT diyakini sangat sulit. Jika Anda menerima dugaan ini maka sangat masuk akal untuk melihat pengurangan yang membuktikan universalitas masalah NP karena masalahnya sulit. (Mengapa para peneliti menemukan P tidak sama dengan NP lebih mungkin adalah masalah yang berbeda, ada beberapa posting blog di blog teori tentang itu.)

Bagian dari alasan kami mengganti batas bawah dengan hasil universalitas (yaitu ada pengurangan dari setiap masalah di kelas ke masalah) adalah kurangnya keberhasilan kami dalam membuktikan batas bawah umum yang baik (ini sesuai dengan kondisi pengetahuan saat ini) bahwa SAT dapat diselesaikan dalam waktu deterministik linier).

Sebenarnya, penemuan Alaska akan memiliki efek sebaliknya, setidaknya pada awalnya. Sejak itu meluas sejauh barat, itu akan membuat orang berpikir bahwa, hey, mungkin ada adalah sebuah jembatan tanah, setelah semua (analogi makhluk, hey, mungkin P  =  NP karena ini baru NP masalah -Lengkap terlihat seperti seperti calon yang baik untuk memiliki solusi polinomial-waktu). Namun, begitu Alaska telah dieksplorasi secara menyeluruh dan tidak ada jembatan darat yang ditemukan, orang mungkin akan lebih yakin daripada sebelumnya bahwa Asia dan Amerika terpisah.

pertanyaannya memperkenalkan analogi / metafora tertentu yang tidak banyak digunakan oleh para ahli dan hanya berfokus pada P / NP & tidak menyebutkan kelas kompleksitas lainnya, sedangkan para ahli cenderung melihatnya sebagai alam semesta entitas yang saling berhubungan besar seperti dalam diagram luar biasa yang dibuat oleh Kuperberg . akan rapi untuk menyusun daftar besar analogi kelas kompleksitas, ada banyak analogi seperti itu. itu berbicara tentang "pengarsipan" masalah terbukti sebagai NP lengkap dan "kegembiraan atas pendekatan baru".

kita dapat memahami bahwa ada "kegembiraan" awal dalam menemukan kelas lengkap NP, tetapi beberapa "kegembiraan" telah memudar setelah sekarang selama empat dekade upaya intens untuk membuktikan P ≠ NP tampaknya tidak pergi ke tempat yang menjanjikan dan beberapa peneliti merasa bahwa kita tidak lebih dekat. sejarah penuh dengan para peneliti yang menghabiskan waktu bertahun-tahun menangani masalah tanpa ada kemajuan nyata atau kadang-kadang dengan penyesalan kemudian. sehingga NP lengkap dapat berfungsi (untuk meminjam analogi Aaronson) sebagai semacam "pagar listrik", peringatan / peringatan untuk tidak terlalu terlibat dalam upaya (di sini secara harfiah, dalam banyak cara lebih dari satu) masalah "sulit".

memang benar ada aspek utama "katalog" masalah lengkap NP yang masih berlanjut. namun penelitian besar-besaran "halus" tentang masalah lengkap NP kunci (SAT, deteksi klik, dll) terus berlanjut. (sebenarnya fenomena yang sangat mirip terjadi pada masalah yang tidak dapat diputuskan: pernah terbukti tidak dapat dipastikan, seolah-olah mereka diperintah sebagai "tanah tidak bertuan" untuk penyelidikan lebih lanjut.)

sehingga semua masalah NP lengkap terbukti setara sejauh teori saat ini dan ini kadang-kadang muncul dalam dugaan yang mencolok seperti Berman-Hartmanis dugaan isomorfisme . Para peneliti berharap bahwa ini akan berubah suatu hari nanti.

pertanyaan ini dilabeli soft-questiondengan alasan yang bagus. Anda tidak akan menemukan banyak ilmuwan serius yang membahas analogi dalam makalah mereka, yang mengarah ke ilmu pengetahuan populer , lebih suka berfokus pada ketepatan / kekakuan matematika (dan seperti yang ditekankan dalam pedoman komunikasi untuk kelompok ini). namun ada beberapa nilai di sini untuk mendidik & berkomunikasi dengan orang luar / orang awam.

berikut adalah beberapa "kontra-analogi" untuk orang awam bersama dengan "petunjuk penelitian" untuk konsep-konsep tersebut. ini bisa dibuat menjadi daftar yang lebih panjang.

• ada analogi wilayah dalam pertanyaan. tetapi lebih masuk akal untuk memikirkan wilayah utama teori kompleksitas termasuk dalam kelas yang dikenal sebagai terra incognita . dengan kata lain ada daerah P berpotongan NP. P dan NP keduanya cukup dipahami tetapi tidak diketahui apakah wilayah P ⋂ NP-hard (P intersect NP-hard) kosong atau tidak.

• Aaronson baru-baru ini memberikan metafora dari dua jenis spesies katak yang tampaknya berbeda yang tidak pernah bercampur untuk P / NP. dia juga menyebut "pagar listrik tak terlihat" di antara keduanya.

• fisika partikel mempelajari model standar. fisika mempelajari komposisi partikel seperti halnya teori kompleksitas mempelajari komposisi kelas kompleksitas. dalam fisika ada beberapa ketidakpastian tentang bagaimana beberapa partikel memunculkan partikel lain ("menetapkan batas") seperti dalam teori kompleksitas.

• "the complex zoo" , seperti banyak hewan eksotis yang memiliki kemampuan berbeda, sebagian kecil / lemah & sebagian besar / kuat.

• kelas kompleksitas seperti kontinum ruang / waktu yang mulus seperti yang terlihat dalam teorema hierarki Waktu / Ruang dengan "titik-titik transisi" yang penting (secara mengejutkan cukup analog dengan transisi fase materi fisik) antara berbagai keadaan.

• mesin Turing adalah mesin dengan "komponen bergerak" dan mesin bekerja yang setara dengan pengukuran energi , dan mereka memiliki pengukuran waktu / ruang . jadi kelas kompleksitas dapat dilihat sebagai "energi" yang terkait dengan transformasi input-output kotak hitam.

• ada banyak kemungkinan analog dari sejarah Matematika yaitu masalah mengkuadratkan lingkaran, menemukan solusi aljabar untuk persamaan kuintik, dan sebagainya.

• Dunia Impaggliazo

• Buku baru Fortnows berisi banyak analogi sains populer untuk pertambangan.

• Enkripsi / Dekripsi: Turing terkenal mengerjakan ini selama Perang Dunia II dan banyak teorema yang membuktikan tentang perbedaan dalam kelas kompleksitas mungkin tampak analog dengan masalah dekripsi. ini dibuat lebih solid dengan makalah seperti Natural Proofs di mana pemisahan kelas kompleksitas terkait langsung dengan "melanggar" generator nomor acak semu.

• Kompresi / dekompresi: kelas kompleksitas yang berbeda memungkinkan untuk / mewakili jumlah kompresi data yang berbeda. misalnya misalkan P / poli mengandung NP. itu berarti bahwa ada entitas "kecil" (yaitu sirkuit) yang dapat "menyandikan" "lebih besar" masalah lengkap NP, yaitu struktur (data) yang lebih besar dapat "dikompresi" secara efisien menjadi struktur (data) yang lebih kecil.

• sepanjang analogi kebun binatang / hewan, ada aspek Buta dan gajah yang kuat terhadap teori kompleksitas. bidang ini tampaknya masih / mungkin dalam tahap awal dari busur yang sangat panjang (ini tidak masuk akal atau belum pernah terjadi - dari bidang matematika lain yang memiliki rentang berabad-abad atau bahkan milenia) dan banyak pengetahuan dapat dilihat sebagai parsial, terputus-putus, dan terfragmentasi.

jadi singkatnya pertanyaannya tentang "optimisme yang terkait dengan pengurangan". para ilmuwan umumnya menahan diri dari emosi atau bahkan menertawakannya kadang-kadang dalam pencarian mereka yang murni logis. ada keseimbangan antara pesimisme jangka panjang dan optimisme hati-hati di lapangan & sementara ada beberapa ruang untuk informalitas, semua peneliti serius harus berusaha menuju imparsialitas dalam sikap profesional mereka sebagai bagian dari deskripsi pekerjaan. dapat dimengerti bahwa ada fokus pada kemenangan kecil dan inkrementalisme dan tidak "terbawa".