Jelaskan masalah P = NP hingga 10 tahun

Ini adalah pertanyaan pertama saya di situs ini. Saya mengambil kursus master tentang teori perhitungan. Bagaimana Anda akan menjelaskan masalah P = NP kepada seorang anak berusia 10 tahun dan mengapa ia memiliki imbalan uang seperti itu?

Anda menerima?

Saya akan memperbarui pertanyaan karena kepalaku sudah mengerti.

Saya menggunakan 3 slide ini untuk menunjukkan mengapa begitu sulit (mustahil?) Untuk membuat algoritma cepat untuk masalah NP:

Dalam ceramah ini Scott Aaronson menjawab pertanyaan itu.

TEDxCaltech - Scott Aaronson - Fisika di Abad ke-21: Bekerja keras di Bayangan Feynman

Peringatan: Tolong, JANGAN tampilkan pembicaraan ini langsung ke nenek Anda / 10 tahun. Mengapa? tonton itu dan kamu akan tahu. ;-)

EDIT:
Berikan anak 8 puzzle ratu untuk dipecahkan. Juga beri dia batas waktu.

Jika dia "menemukan" solusi, maka dia adalah anak yang cerdas, Anda dapat segera mulai mengajarinya CS. :)
Lain Anda tunjukkan solusinya dan minta dia untuk "memeriksa" apakah itu benar.

$\mathsf{P}$ adalah serangkaian masalah di mana komputer dapat "menemukan" solusi dengan mudah.

$\mathsf{NP}$ adalah serangkaian masalah di mana komputer tidak dapat "menemukan" solusi dengan mudah tetapi dapat "memeriksa" solusinya dengan mudah.

Jika kita dapat "memeriksa" suatu solusi dengan mudah maka mengapa kita tidak dapat "menemukannya" dengan mudah?

Apa yang Anda lakukan di CS adalah Anda menyelesaikan masalah atau membuktikan bahwa tidak ada yang bisa.

Jika seseorang menemukan algoritma yang membuatnya mudah untuk "menemukan" solusi untuk masalah NP maka tabel akan terlihat seperti dan . P=N

Dan jika seseorang membuktikan bahwa tidak ada yang dapat menemukan algoritma untuk "menemukan" solusi untuk masalah maka tabelnya tetap sama dan .P ≠ N $\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Salah satu hal utama yang orang gunakan untuk komputer adalah mencari. Program-program seperti Google bahkan disebut "mesin pencari," dan digunakan jutaan kali sehari. Sebuah komputer baru-baru ini mengalahkan manusia di Jeopardy karena ia dapat mencari melalui banyak data, sangat cepat.

Tetapi beberapa hal sulit dilakukan bahkan oleh komputer. Kedengarannya aneh, bukan? Salah satu contoh adalah multiplikasi terbalik. Tentu saja jika saya mengatakan "Berapa 5 kali 3?" Anda bisa mengatakan "15" dalam nanosecond, whooosh! Tapi apa jawaban untuk, "Dua angka apa yang digandakan bersama dengan angka 21?" (Tunggu jawabannya, 7 x 3.) Benar! Sekarang, apa dua angka yang dikalikan bersama dengan 23? (Tunggu jawabannya, atau frustrasi.)

Dua angka yang dikalikan bersama yang sama dengan 23 adalah 1 dan 23 itu sendiri. Butuh beberapa pemikiran, bukan? Dan 23 adalah angka kecil. Pikirkan jika jumlahnya ratusan digit. Dan masalahnya adalah, program terbaik di dunia tidak dapat membalikkan perkalian jauh lebih baik daripada yang mungkin dilakukan oleh anak berusia 7 tahun, hanya menguji satu angka, lalu yang berikutnya, dan kemudian yang berikutnya. Komputer dapat melakukannya dengan lebih cepat , tetapi kita tidak benar-benar tahu bagaimana cara memberitahu komputer untuk melakukannya dengan lebih cerdas . Orang-orang mendapatkan gelar PhD dalam hal ini, dan mereka hanya tahu bagaimana cara memberitahu komputer untuk melakukan multiplikasi terbalik sedikit lebih pintar.

Jadi mungkin tidak ada cara yang lebih pintar. Tapi mungkin ada, dan kami belum menemukannya. Singkatnya, masalah P / NP: jika saya dapat langsung mengenali jawaban - 1 kali 23 adalah 23, ya - apakah itu membantu saya mencari jawaban lebih cepat? Orang-orang berpikir itu sangat penting sehingga orang yang menemukan jawabannya, ya atau tidak, akan memenangkan satu juta dolar.

Saya pikir masalah P vs NP bisa dijelaskan dengan sangat lembut dalam hal Sudoku. Saya berasumsi anak sepuluh tahun yang dimaksud akrab dengan Sudoku. Saya akan mencoba mendukung kesederhanaan daripada ketelitian dalam penjelasan saya.

Ini adalah usaha saya untuk menjelaskan P = NP kepada anak sepuluh tahun yang hipotetis:

Jika Anda memiliki teka-teki Sudoku yang belum selesai, dan Anda ingin menyelesaikannya, itu bisa sangat sulit dilakukan. Di sisi lain, jika teman Anda menyelesaikan masalah dan Anda mahir berhitung, tidak terlalu sulit untuk memeriksa apakah solusi teman Anda untuk teka-teki itu benar.

Pertanyaan P = NP menanyakan apakah ada proses langkah-demi-langkah yang sangat cepat untuk menyelesaikan teka-teki Sudoku yang belum selesai. Proses langkah demi langkah harus sangat jelas dan mudah dipahami sehingga bahkan komputer dapat memahaminya dan menggunakannya untuk memecahkan teka-teki Sudoku secara otomatis dan sangat cepat. Jika ada proses selangkah demi selangkah yang demikian cepat, itulah yang oleh para ahli matematika disebut sebagai "algoritma waktu polinomial" (saya akan menjelaskan apa artinya itu ketika Anda lebih tua).

Faktanya, ilmuwan komputer dan pemrogram komputer telah mengidentifikasi banyak teka-teki lain dan masalah yang sangat penting yang sama sulitnya dengan Sudoku. Sangat penting untuk mengetahui apakah masalah ini dapat diselesaikan, karena komputer dapat membantu kita melakukan banyak hal lebih cepat jika mereka bisa. Misalnya, mereka dapat membantu kami menjadwalkan kereta lebih efisien, memecahkan kode rahasia, dan bahkan mungkin membangun bantuan untuk membangun komputer yang benar-benar pintar yang mampu melakukan kecerdasan buatan.

Akan ada banyak hal yang sangat baik yang akan terjadi jika orang dapat menyelesaikan P = NP. Tentu saja, akan ada beberapa masalah, karena akan lebih sulit untuk menggunakan kode rahasia untuk merahasiakan pesan pribadi.

Kebanyakan ahli matematika pintar berpikir bahwa P = NP tidak benar. Dengan kata lain, kebanyakan orang berpikir bahwa tidak ada yang akan mampu memecahkan teka-teki Sudoku yang sangat sulit dengan cepat. Namun, tidak ada yang pernah dapat membuktikan bahwa P tidak sama dengan NP sebelumnya, jadi sebuah organisasi bernama Clay Mathematics Institute menawarkan hadiah satu juta dolar untuk bukti pertama bahwa P = NP benar, atau untuk yang pertama bukti bahwa itu salah.

Seperti yang Anda lihat, saya mengambil bagian "jelaskan kepada anak sepuluh tahun" secara harfiah. :)

Semoga ini membantu.

Beginilah cara saya menjelaskannya kepada ibu saya, semoga akan membantu Anda :)

Ada masalah yang mudah untuk menemukan solusinya (P, tetapi kurang menyebutnya "mudah dipecahkan"), masalah yang mudah diperiksa apakah solusi yang diberikan benar (NP, tetapi sebut saja "mudah diperiksa") ), dan masalah yang tidak mudah dipecahkan atau juga tidak mudah diperiksa. Untuk kesederhanaan, anggaplah bahwa "Mudah" didefinisikan secara formal, dan bahwa setiap masalah memiliki solusi yang unik.

Sekarang, orang telah dapat membuktikan (menggunakan matematika) hubungan yang menarik antara dua pengertian "mudah dipecahkan" dan "mudah diperiksa", sehingga beberapa masalah tidak mudah dipecahkan, dan bahwa beberapa orang lain tidak mudah diperiksa. Contoh dasar dari hasil tersebut adalah bahwa masalah yang mudah dipecahkan juga mudah diperiksa: temukan saja solusinya dan bandingkan dengan solusi yang diberikan.

Cukup menggoda, untuk banyak masalah praktis (seperti memutuskan apakah ada kemungkinan tugas siswa untuk profesor dan ruang kelas, ketika ada sangat sedikit margin) tidak diketahui apakah ada cara "mudah" untuk menyelesaikannya, tetapi diketahui cara memeriksa dengan mudah apakah suatu solusi benar atau tidak. Orang-orang mencoba banyak dan gagal, kemudian mencoba membuktikan bahwa itu tidak mungkin dan gagal juga: mereka tidak tahu. Beberapa orang berpikir bahwa semua masalah yang mudah diperiksa dapat dipecahkan dengan mudah (kita hanya harus memikirkannya lebih lanjut), beberapa berpikir sebaliknya, bahwa kita seharusnya tidak membuang waktu untuk mencari solusi mudah dari masalah ini.

Apa yang kami temukan adalah bagaimana menunjukkan hubungan antara masalah (misalnya jika Anda tahu cara pergi ke sekolah, Anda tahu cara pergi ke toko roti yang ada di depan) dan masalah yang mudah diperiksa yang terkait dengan semua masalah lain yang mudah diperiksa ( Lengkap-NP, tetapi sebut mereka "masalah utama") sehingga jika seseorang, suatu hari, menunjukkan bahwa salah satu masalah utama mudah diselesaikan, maka semua masalah yang mudah diperiksa juga mudah dipecahkan (yaitu P = NP). Di sisi lain, jika seseorang menunjukkan bahwa salah satu masalah utama tidak dapat dengan mudah dipecahkan, maka tidak ada orang lain yang dapat dengan mudah dipecahkan (yaitu P <> NP).

Jadi pertanyaannya adalah menggiurkan, dan relatif penting dalam praktik (walaupun beberapa orang berpendapat bahwa kita harus lebih fokus pada definisi alternatif "mudah"), dan orang-orang menginvestasikan banyak uang dan waktu dalam debat.

Michael Sipser menjelaskan masalah P vs NP dengan cara yang sangat intuitif dalam video ini .

Saya agak skeptis tentang kemungkinan menjelaskan masalah itu kepada seorang anak berusia 10 tahun, atau bahkan kepada orang awam, tanpa menimbulkan kesalahan penyajian konsep-konsep kunci.

Semua penjelasan yang dirumuskan dalam istilah "kemudahan" vs "kekerasan" untuk menemukan vs memeriksa solusi mengasumsikan tesis Cobham, yang bisa dibilang salah dalam kasus umum, dan dapat dianggap sedikit lebih dari sekadar aturan praktis.

strategi pemenang untuk berbagai permainan papan klasik misalnya kapal perang atau (baru-baru ini) video game telah terbukti NP lengkap & ini adalah cara / sudut yang sangat baik untuk menyajikan / menggambarkan beberapa teori inti ke pemula.

kapal perang sebagai masalah keputusan NP lengkap Merlijn Sevenster ICGA jurnal September 2004

kapal penyapu ranjau adalah NP lengkap FAQ oleh ahli matematika RW Kaye. Masalah Spring Intelligence 2000 (volume 22 nomor 2, halaman 9--15)

Bermain game adalah pekerjaan berat, tetapi harus ada yang melakukannya! makalah arxiv karya Giovanni Viglietta. menganalisis kompleksitas komputasi Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, dan Starcraft.

Pacman adalah artikel majalah teknologi ekstrem keras di atas kertas

Dan ini saya ambil masalah.

Kido!

Anda tahu kita menghadapi banyak masalah dalam hidup kita. Anda bisa mengatakan tantangan. Ada yang sulit ada yang lebih mudah. Misalnya, Anda sering perlu menambahkan dua angka. Dan tadi malam, kami berada di papan catur dan kami harus menang melawan tetangga kami. Nah, menambahkan dua angka adalah masalah yang sederhana dan lurus dengan langkah-langkah terbatas yang terlibat. Masalah seperti ini disebut masalah kelas P karena ada banyak masalah yang cukup mudah dengan langkah-langkah terpisah yang harus diulang berulang kali untuk mendapatkan solusi.

Di sisi lain, tadi malam di pertandingan dada kami, apa strategi terbaik untuk memenangkan pertandingan? Kita bisa memindahkan pion pertama satu langkah, atau pion kedua satu langkah, atau kita bisa memindahkan pion kedua dua langkah dan pion pertama satu langkah sehingga Anda melihat ada banyak dan banyak kemungkinan. Tetapi apakah ada cara untuk kita atau penerima yang memberi kita serangkaian gerakan lengkap yang menghasilkan yang terbaik dan untuk skakmat? Jadi Anda lihat itu berhenti keras karena ada begitu banyak kemungkinan satu setiap langkah. Miliaran dan Miliaran seperti kata Carl Sagan.

Tetapi sayang bagaimana jika saya memberi tahu Anda semua posisi dewan dan bertanya apakah ini skakmat? Tentunya Anda akan dapat dengan cepat memberi tahu dalam beberapa pemeriksaan apakah ada langkah hukum yang tersisa untuk raja.

Jadi masalah seperti itu yang sulit dipecahkan tetapi jika solusi mereka mudah diverifikasi dalam beberapa langkah sederhana, mereka disebut masalah NP.

Sekarang Anda bertanya apa artinya P = NP? Sebenarnya pertanyaan ini berarti apakah ada cara agar kita dapat menemukan solusi yang lebih sederhana untuk menemukan strategi terbaik atau daftar gerakan untuk permainan catur tanpa melalui semua miliaran kemungkinan seperti yang kita lakukan untuk penambahan sederhana? Pertanyaan sederhana ini belum terjawab. Kami tidak memiliki bukti untuk kebenaran itu atau untuk penolakan tetapi jika kami melakukannya, itu akan menjadi terobosan. Jika ternyata benar, peradaban kita mungkin bisa memecahkan masalah yang sangat kompleks dengan mengubahnya menjadi masalah kelas P. Orang akan dapat memecahkan kata sandi dengan beberapa detik, pesan akan didekripsi dan lebih banyak lagi dan itulah sebabnya masalah ini dianggap sebagai salah satu masalah terpenting milenium.