Mengajar kelengkapan NP - Reduksi Turing vs reduksi Karp

25

Saya tertarik pada pertanyaan tentang cara terbaik untuk mengajarkan kelengkapan NP ke jurusan ilmu komputer. Secara khusus, haruskah kita mengajarkannya menggunakan pengurangan Karp atau menggunakan pengurangan Turing?

Saya merasa bahwa konsep pelengkapan dan pengurangan NP adalah sesuatu yang harus dipelajari oleh setiap ilmu komputer. Namun, ketika mengajarkan kelengkapan NP, saya perhatikan bahwa penggunaan pengurangan Karp memiliki beberapa kelemahan.

Pertama-tama, pengurangan Karp tampaknya tidak perlu membingungkan bagi beberapa siswa. Gagasan intuitif tentang pengurangan adalah "jika saya memiliki algoritma untuk menyelesaikan masalah X, maka saya dapat menggunakannya untuk menyelesaikan masalah Y juga". Itu sangat intuitif - tetapi memetakan jauh lebih baik untuk pengurangan Turing daripada pengurangan Karp. Sebagai hasilnya, saya melihat siswa yang mencoba untuk membuktikan kelengkapan NP bisa disesatkan oleh intuisi mereka dan membentuk bukti yang salah. Mencoba untuk mengajarkan kedua jenis reduksi dan menekankan aspek pengurangan Karp ini kadang-kadang terasa sedikit seperti formalisme yang tidak perlu dan mengambil waktu kelas yang tidak perlu dan perhatian siswa pada apa yang terasa seperti detail teknis yang tidak penting; itu tidak jelas mengapa kita menggunakan gagasan pengurangan yang lebih terbatas ini.

Saya benar-benar memahami perbedaan antara pengurangan Karp dan pengurangan Turing (Cook), dan bagaimana mereka mengarah pada gagasan berbeda tentang kelengkapan NP. Saya menyadari bahwa pengurangan Karp memberi kita granularitas yang lebih baik dari perbedaan antara kelas kompleksitas. Jadi, untuk studi serius tentang teori kompleksitas, pengurangan Karp jelas merupakan alat yang tepat. Tetapi bagi siswa ilmu komputer yang baru belajar ini dan tidak akan pernah masuk ke teori kompleksitas, saya tidak yakin apakah perbedaan yang lebih baik ini sangat penting bagi mereka untuk diekspos.

Akhirnya, sebagai seorang mahasiswa, saya ingat merasa bingung ketika saya menemukan masalah seperti "tautologi" - misalnya, diberikan formula boolean, periksa apakah itu tautologi. Yang membingungkan adalah bahwa masalah ini jelas sulit: algoritma waktu polinomial apa pun untuk itu akan menyiratkan bahwaP=NP; dan memecahkan masalah ini jelas sama sulitnya dengan memecahkan masalah tautologi. Namun, meskipun secara intuitif tautologi sama sulitnya dengan kepuasan, tautologi bukan NP-keras. Ya, saya mengerti hari ini mengapa ini terjadi, tetapi pada saat itu saya ingat sedang bingung dengan ini. (Apa yang terlintas di kepala saya ketika saya akhirnya mengerti adalah: Mengapa kita menggambar perbedaan antara NP-hard dan co-NP-hard, sih? Itu tampaknya buatan dan tidak termotivasi dengan baik oleh latihan. Mengapa kita lebih fokus pada NP? dari pada co-NP? Mereka tampaknya sama-sama alami. Dari perspektif praktis, co-NP-hardness pada dasarnya memiliki konsekuensi praktis yang sama dengan NP-hardness, jadi mengapa kita semua terpaku pada perbedaan ini? Ya, saya tahu jawaban, tetapi sebagai seorang siswa, saya ingat ini hanya membuat subjek merasa lebih misterius dan kurang termotivasi.)

Jadi, pertanyaan saya adalah ini. Saat kami mengajarkan kelengkapan NP kepada siswa, apakah lebih baik mengajar menggunakan pengurangan Karp atau pengurangan Turing? Adakah yang mencoba mengajarkan konsep kelengkapan NP menggunakan reduksi Turing? Jika demikian, bagaimana hasilnya? Apakah akan ada jebakan atau kerugian yang tidak jelas jika kita mengajarkan konsep menggunakan reduksi Turing, dan melewatkan masalah konseptual yang terkait dengan pengurangan Karp?


Terkait: lihat di sini dan di sini , yang menyebutkan bahwa alasan mengapa kita menggunakan pengurangan Karp dalam literatur adalah karena hal itu memungkinkan kita untuk membedakan antara kekerasan-NP dan kekerasan bersama-NP. Namun, tampaknya tidak memberikan jawaban yang berfokus pada perspektif pedagogis apakah kemampuan ini sangat penting untuk tujuan pembelajaran kelas algoritma yang harus diambil oleh setiap CS mayor. Lihat juga di sini di cstheory.SE , yang memiliki diskusi serupa.

DW
sumber
Pengamatan Motivasi: Turing-mengurangi ke masalah dalam NP tidak diketahui menyiratkan . XNP
1
@ RickyDemer, mengerti - tetapi ketika kami mencoba menunjukkan masalah itu sulit, kami tidak benar-benar peduli apakah ada dalam NP atau tidak, sehingga itu tidak memotivasi saya secara sangat efektif. Dan, menunjukkan masalah sulit adalah aplikasi utama NP, NP-kelengkapan, NP-hardness, dll.X
DW
1
Saya tidak melihat banyak perbedaan. Gagasan Cook tentang "meminta solusi dari masalah lain" adalah wajar untuk pemrograman , tetapi bagi orang-orang yang memiliki latar belakang yang lebih abstrak (beberapa matematika terpisah di bawah ikat pinggang mereka) pemetaan antara contoh masalah juga alami.
vonbrand

Jawaban:

10

Saya akan mengatakan sangat pasti mengajar menggunakan pengurangan Karp (banyak-satu). Terlepas dari manfaat menggunakan pengurangan Turing (Masak) poly-time, reduksi Karp adalah model standar.

Semua orang menggunakan Karp dan perangkap utama mengajar Cook adalah bahwa Anda akan berakhir dengan seluruh kelas siswa yang menjadi bingung secara patologis setiap kali mereka membaca buku teks atau mencoba membahas subjek dengan siapa saja yang tidak diajari oleh Anda.

Saya setuju bahwa pengurangan Cook dalam beberapa hal lebih masuk akal dan bahwa tidak ada perbedaan antara kekerasan NP dan kekerasan TNP dalam istilah praktis, dalam arti bahwa keduanya berarti "Masalah ini cukup sulit dan Anda tidak akan mendapatkan algoritma umum, efisien, tepat yang dapat mengatasi contoh besar. " Di sisi lain, perbedaan antara NP dan coNP tidak sepenuhnya merupakan artefak dari teori yang didasarkan pada pengurangan Karp: Anda tidak sering berbicara tentang grafik yang tidak memiliki 3-colourability atau di mana setiap set  berisi simpul di setidaknya satu sisi. Entah bagaimana, versi "alami" masalah sering kali tampaknya dalam NP daripada coNP.k

David Richerby
sumber
7

Lebih baik mengajar keduanya ! Jurusan ilmu komputer harus tahu tentang keduanya.

Saya tidak tahu siapa pun yang menggunakan reduksi Cook untuk mengajar kelengkapan NP, jelas teori kompleksitas tidak, teori non-kompleksitas biasanya mengikuti apa definisi standar sejak makalah Karp dan digunakan di semua buku teks (yang saya tahu). Ini akan menyebabkan banyak kebingungan bagi mereka nanti jika Anda tidak mengikuti terminologi standar.

Pengurangan Cook pada dasarnya memecahkan masalah menggunakan subrutin kotak hitam. Mereka mudah dijelaskan dan memotivasi jika siswa Anda memiliki pengalaman pemrograman. Mereka sangat penting karena tanpa pengurangan Cook Anda tidak dapat mendiskusikan pengurangan antara masalah pencarian, masalah optimasi, dll.

NPNPPNPNP

NPcoNPNPNPNPPNP

xAf(x)B

Kaveh
sumber
2
NPNPNPNP
@DW maksud Anda "Masak" di tempat (yang kedua dan ketiga) "Karp" di komentar Anda? Anda masih dapat membuktikan bahwa masalah sulit menggunakan Cook, bukan itu masalahnya. Masalahnya adalah bahwa NP tidak ditutup di bawah mereka, yaitu pengurangan Cook tidak menjaga masalah diverifikasi secara efisien.
Kaveh
2
Ups, ya, maksudku Cook, bukan Karp. (argh!) Saya mengerti bahwa NP tidak ditutup di bawah pengurangan Cook, tetapi dapatkah Anda menguraikan mengapa itu merupakan masalah, dari perspektif bagaimana kami mengajarkan algoritma kepada sarjana? Apa masalah pedagogis atau konseptual yang dihasilkannya? Apa konsekuensi negatifnya jika kita mengajarkan algoritma seperti itu, dan baru saja mengakui / menerima bahwa NP tidak ditutup di bawah pengurangan Cook? Misalnya, apakah itu akan menyebabkan beberapa kesalahpahaman konseptual yang bermasalah di antara siswa?
DW
-3

Gagasan intuitif tentang pengurangan adalah "jika saya memiliki algoritma untuk menyelesaikan masalah X, maka saya dapat menggunakannya untuk menyelesaikan masalah Y juga".

cara yang menarik untuk mendekati masalah pengajaran khusus ini adalah untuk menyadari bahwa kelengkapan NP memiliki kesamaan dan analogi dengan ketidakpastian yang juga tidak intuitif. siswa masuk kelas hanya pernah mendengar tentang algoritma yang berhenti. tetapi teorema prinsip TCS adalah bahwa ada masalah yang tidak ada solusi pasti, yaitu masalah penghentian. dan sebenarnya masalah yang tidak dapat dipastikan dapat mulai terlihat jauh dari yang direncanakan, dan tampaknya agak ada di mana-mana.

jadi, teori ini memberi tahu kita cara memandang komputasi secara fundamental sebagai proses yang dapat mengembalikan jawaban dalam beberapa keadaan. dalam keadaan lain, mungkin tidak. untuk kelengkapan dan kepastian NP, pertanyaan mendasar dan paling umum adalah, "apakah ada algoritma yang kembali Ydalam waktu P". tapi ini tidak mengatakan apa-apa tentang algoritma yang kembali Ndalam waktu P. suatu algoritma dapat kembali Ydalam waktu P untuk satu contoh tetapi tidak mengembalikan jawaban pada contoh lain. teori ini memberi tahu kita bahwa ada perbedaan nyata di sini yang harus kita perhatikan. jika tidak intuitif, itu berarti intuisi fundamental kita perlu disesuaikan kembali (seperti yang sering terjadi dalam pengajaran teoretis).

ay
sumber
dengan kata lain, tampaknya ada algoritma yang kembali Ydalam waktu P tetapi juga membutuhkan waktu "lebih lama" daripada waktu P untuk kembali Ndan teorinya didasarkan pada / berorientasi / fokus sekitar waktu yang diperlukan untuk menjawab Y.
vzn
1
Setiap siswa yang telah menulis lebih dari lima program akrab dengan konsep "suatu algoritma yang tidak berhenti" dari pengalaman pribadi langsung.
David Richerby
hanya mencoba mendefinisikan CoNP dengan cara yang lebih intuitif seperti yang diminta berdasarkan pengalaman / analogi sehari-hari. Saya selalu menemukan itu tidak intuitif. apakah ada yang punya cara yang lebih baik?
vzn