Setiap hari bertemu dengan masalah NP-lengkap

Mark Dominus mengumpulkan beberapa contoh pengurangan polinomial-waktu dari berbagai masalah NP-hard untuk pencocokan "ekspresi reguler" . Membayangkan verifikasi polinomial-waktu bukanlah lompatan besar.

Bagaimana Anda menggambarkan NP-lengkap kelas untuk sarjana atau teman-teman di bidang lain yang ingin memahami keributan baru-baru ini atas makalah Deolalikar?

Contoh favorit saya untuk digunakan dengan teman non-CS adalah yang ini:

Abraham, A. Blum, Sandholm. Algoritma kliring untuk pasar pertukaran barter: memungkinkan pertukaran ginjal secara nasional. EC07.

Pasar pertukaran ginjal pada dasarnya adalah bentuk penutupan siklus yang terbatas. Saya suka contoh ini karena a) mudah untuk menjelaskan intinya (jika Anda meninggalkan beberapa detail yang lebih teknis) dan b) itu salah satu dari sedikit contoh yang saya tahu di mana algoritma yang lebih baik benar-benar dapat menyelamatkan nyawa!

Contoh favorit saya yang kedua adalah masalah rumah sakit dan penduduk (alias masalah penerimaan di perguruan tinggi). Setiap rumah sakit memberi peringkat semua penghuni (lulusan mahasiswa kedokteran) dan penghuni memberi peringkat rumah sakit. Setiap rumah sakit memiliki sejumlah slot. Dari sana itu masalah pencocokan yang stabil dan dapat diselesaikan dalam waktu polinomial.

Namun pada kenyataannya, pasangan dapat memasuki sistem (ya, memang ada sistem ) bersama-sama, sehingga sistem tidak akan, misalnya, berpisah pasangan menikah yang sama-sama mengajukan permohonan tempat tinggal. Penambahan pasangan membuat masalah NP-lengkap. Selain mudah dijelaskan, ini juga menunjukkan bagaimana pengenalan koneksi jarak jauh dapat menginduksi kelengkapan NP.

Beberapa masalah "setiap hari" yang NP-hard, dirumuskan dengan tepat:

• Menetapkan kelas universitas ke timeslots untuk meminimalkan konflik penjadwalan.

• Menetapkan tamu pernikahan ke kursi sehingga teman duduk di meja yang sama, tetapi musuh tidak.

• Merencanakan perjalanan untuk mengunjungi semua tempat wisata dalam daftar, sehingga meminimalkan mengemudi.

Masalah salesman keliling tampaknya dapat diakses ... setidaknya di mana saya berada, ini tampaknya menjadi masalah CS yang paling populer di kalangan orang-orang non-CS sejauh ini. Saya juga menemukan ilustrasi Vertex Cover yang cukup menarik, seperti yang diperkenalkan oleh instruktur algoritma saya:

Anda memiliki jaringan jalan dan ingin memastikan bahwa jika mobil macet bahan bakar, ada pompa bensin di setidaknya satu ujung jalan.

Sebagai perencana kota, Anda ingin meminimalkan biaya dengan membangun jumlah pompa bensin sesedikit mungkin. Ini pada dasarnya adalah masalah penutup verteks, dan saya telah menemukan beberapa keberhasilan dalam menunjukkan bahwa meskipun Anda tidak berharap untuk menemukan penutup simpul optimal dalam waktu polinomial, Anda dapat menemukan sesuatu yang hanya merupakan faktor dua faktor dalam waktu polinomial, dengan hanya mengambil kedua titik akhir dari pencocokan maksimum (well, detail terakhir mungkin dihilangkan tergantung pada seberapa tajam audiens Anda - terutama karena algoritma MM tidak persis dua-liner).

Adapun contoh 'lompatan dalam kompleksitas' dengan perubahan kecil dalam sifat masalah, saya pikir perbedaan antara memeriksa 2-colorability dan 3-colorability adalah contoh yang baik. Dengan semua publisitas seputar teorema empat warna, orang mungkin juga menunjukkan bahwa memeriksa apakah peta dapat diwarnai dengan baik hanya dengan tiga warna, bukan empat adalah sulit, meskipun kita tahu bahwa itu selalu dapat diwarnai dengan empat warna. Banyak orang merasa ini cukup mengejutkan.

Situasi lain yang cukup alami adalah masalah pemulihan kebuntuan dalam sistem operasi. Ini dimodelkan oleh masalah NP-set lengkap dari set vertex umpan balik - jumlah terkecil dari simpul yang penghapusannya membuat grafik asiklik - dan saya menemukan ini menjadi contoh yang luar biasa juga (dan dijelaskan lebih lanjut dalam artikel wikipedia).

Saya pikir parkir paralel NP-keras.

Faktanya, masalah yang lebih umum dalam menemukan jalur terpendek dengan kelengkungan terikat yang mengambil objek poligon dari posisi awalnya ke posisi akhir di lingkungan poligon adalah NP-hard. Buktinya dapat ditemukan di sini - http://portal.acm.org/citation.cfm?id=298976

Knapsack cukup mudah untuk dipahami, terutama bagi siapa saja yang harus berurusan dengan koper kecil .. contoh yang bagus jika mereka tahu pemrograman dinamis.

Kegembiraan lain (praktis identik) adalah Subset-sum, karena ia juga memiliki interpretasi fisik yang bagus: bayangkan angka menjadi jarak massa titik yang sama pada penggaris ideal (tanpa massa), dengan titik tumpu pada titik asal. Subset-sum mengatakan: apakah ada subset yang tidak kosong sehingga penggaris akan tetap seimbang? (yaitu, sedemikian rupa sehingga pusat gravitasi adalah titik pendukung bagi penguasa?)

Dalam kedua kasus, tampaknya intuitif bahwa strategi naif mungkin memaksa untuk memeriksa semua himpunan bagian.

Jika mereka memiliki lebih banyak latar belakang, itu bagus untuk menumbuhkan masalah dengan menjatuhkan batasan. Misalnya, mulai dengan masalah aliran maks, mengubahnya menjadi program linier, dan menjadikannya program integer. (Yang paling bagus tentu saja adalah MAX-CUT, karena bagi orang-orang dengan latar belakang lebih banyak Anda juga dapat membuka UGC; Saya menyentuh beberapa di antaranya dalam jawaban MO https://mathoverflow.net/questions/33036/is-quadratic-programming -still-np-hard-if-you-have-bounds-and-a-feasiable-point / 33048 # 33048. ) Juga ada hal-hal yang rapi seperti masalah yang tampaknya serupa yang memiliki kompleksitas yang sangat berbeda (jalur Euler (tepi) linier) waktu, jalur Hamiltonian (simpul) adalah NP-complete).

Konstruksi teka-teki silang adalah NP-Lengkap: Diberikan seperangkat jawaban, cobalah untuk memasukkannya ke dalam kisi.

Saya membuat situs web Tagxedo, http://www.tagxedo.com , generator cloud kata yang sesuai dengan kata-kata (diukur berdasarkan frekuensinya). Hasilnya sangat cantik, tetapi masalahnya mudah terbukti NP-keras (masalah pengepakan).

Menariknya, banyak masalah NP-hard memiliki perkiraan "mudah". Tagxedo tampaknya melakukan pekerjaan yang hampir sempurna dalam banyak kasus. Ini mengarah pada diskusi yang menarik tentang implikasi praktis P vs NP, dan topik pendekatan.

Salah satu teman saya menghabiskan tahun cuti menonton pertandingan baseball di setiap stadion liga utama di Amerika Utara. Tanpa terbang. (Dia tidak cukup berhasil; tiga stadion sedang dibangun tahun itu.)

Karena keberhasilan perusahaan seperti Uber dan Lyft, banyak orang memiliki pengalaman langsung yang sangat mudah diakses dengan masalah NP-lengkap.

Diberikan koleksi pengemudi dan daftar orang yang ingin dijemput di berbagai waktu, apa alokasi penumpang yang paling efisien untuk pengemudi?

Masalah ini (ketika diulang dengan tepat) adalah NPC dan saya membayangkan bahwa orang-orang pada suatu titik bertanya-tanya bagaimana Uber memutuskan untuk memasangkan pengemudi dan penumpang.

Saya biasanya menggunakan SAT sebagai contoh. Saya mengatakan sesuatu seperti "segala macam masalah yang muncul sepanjang waktu dapat ditulis ulang sebagai mencari penugasan yang benar untuk rumus logika besar. Pertanyaan P vs NP adalah apakah ada cara yang secara mendasar lebih mudah untuk menyelesaikan rumus logika ini daripada hanya mencoba semua kemungkinan. Sejauh ini belum ada yang bisa menemukan jalan atau membuktikan bahwa tidak ada jalan keluar yang mudah ".

Masalah Np-selesai seperti Sudoku (pada nxn sqaure) seperti alat Universal yang memungkinkan kita untuk secara efisien menyelesaikan semua masalah yang memiliki solusi yang dapat diverifikasi secara efisien. Satu-satunya persyaratan adalah memiliki metode yang efisien untuk menyelesaikan Sudoku.

$NP$

$n$$p_j$$m$$NP$$p_j$$k$$NP$-lengkap dalam situasi ini. Perhatikan bahwa ini tidak perlu menjadi blok asalkan kita menganggap mereka tidak bisa roboh. Bisa berupa tumpukan kertas, krat, atau piring.

Semoga ini membantu!

Contoh yang dapat diakses secara aneh adalah presentasi singkat oleh Mark Dominus (lihat posting blog terkait ) yang disebut "My Favorite NP-Complete Problem" di mana gambar di bawah ini adalah bagian utama dari ikhtisar dari sampul persis oleh 3-set .

Judul-judul dalam seri video termasuk

• Dansa, Musik, & Buku
• Tangan, Telinga, & Kaki
• Bangun dengan Elmo (tentang tidur, berpakaian, dan menyikat gigi)
• Orang-orang di Lingkungan Anda (tentang petugas pemadam kebakaran, penjaga pantai, dan perawat)

Maksud yang jelas adalah agar setiap video memuat tiga episode dengan tema yang sama yang diambil dari kumpulan topik yang menarik bagi anak-anak.

Bebek aneh dalam seri ini adalah video tentang "bunga, pisang, dan ... rambut."

Terutama ketika melihat masalah Knapsack nanti, masalah NP-complete ini mungkin cocok:

Menebak angka, di mana Anda hanya bisa menebak angka tunggal sampai Anda sudah benar.