Sumber daya untuk mempelajari tentang masalah P vs NP

Saya baru-baru ini diingatkan tentang masalah vs. N P seperti dijelaskan oleh Stephen A. Cook di Clay Mathematics Institute.$\mathsf{P}$$\mathsf{NP}$

Ini menarik minat saya dan saya ingin belajar lebih banyak tentang hal itu. Langkah pertama adalah mendapatkan pemahaman yang lebih dalam tentang masalah dan pemahaman tentang area secara umum.

Bisakah Anda merekomendasikan buku atau sumber daya lain di mana saya dapat mempelajari lebih lanjut tentang masalahnya?

Adalah baik untuk melihat sesama mahasiswa dalam mengejar masalah besar ini, dengan antusiasme yang tinggi. Izinkan saya untuk menawarkan Anda nasihat dari pengalaman saya sendiri.

adalah masalah yang sangat menarik. Implikasi dari jawaban itu sangat besar, terutama dalam kasus bahwa kedua kelas itu sama. Imbalannya luar biasa di banyak tingkatan, dari yang ilmiah altruistik hingga penghargaan uang materialistis. Itu menuntun banyak orang muda yang menghadapi masalah dalam mencoba menyelesaikannya, tanpa pengetahuan terbatas atau tentang hal itu.$P \neq NP$

Mungkin sebagian besar siswa teori melewati fase itu. Anda akan memiliki ide dan berpikir itu benar, tetapi hampir pasti Anda salah. Beberapa orang tidak pernah melewati fase itu dan mempermalukan diri sendiri karena terlalu keras kepala untuk mengakui kesalahan mereka.

Dalam FOCS 2010, Rahul Santhanam membandingkan pertanyaan dengan monster mitos. Butuh banyak pengorbanan dan keberanian bahkan untuk mencoba mengalahkan monster ini. Bagaimanapun, itu mungkin masalah yang paling sulit yang pernah ada. Untuk mendapatkan kesempatan bertarung, Anda harus belajar banyak tentang masalah dan kompleksitas ini secara umum. Anda tidak akan pernah tahu apa yang akan menjadi "kelemahan monster".$P \neq NP$

Jadi saran saya adalah ini: Luangkan waktu Anda untuk mengetahui masalahnya. Setiap kali Anda mencari solusinya, anggaplah Anda salah entah bagaimana dan cobalah untuk menemukan masalahnya. Dengan begitu Anda akan belajar banyak.

Adapun referensi, saya akan merekomendasikan buku Sipser juga. Setelah menyelesaikannya, saya akan merekomendasikan "Kompleksitas Komputasi: Suatu pendekatan modern" oleh Arora dan Barak, sebuah buku yang lebih berorientasi pada kompleksitas, yang membutuhkan pemahaman yang baik tentang konsep komputasi.

Saya sangat menyarankan "Pengantar Teori Komputasi," terutama karena Sipser mencakup setidaknya satu dari hambatan utama untuk menyelesaikan P vs NP, yaitu relativization. Ini berisi bukti yang sangat jelas dari hasil Baker-Gill-Solovay. Saya tidak yakin apakah itu berisi apa pun pada hasil Razborov-Rudich, tetapi ini adalah sumber pengantar yang fantastis, sangat jelas, dan mudah dibaca untuk belajar tidak hanya tentang P vs NP tetapi untuk banyak topik terkait lainnya dalam teori kompleksitas juga. ..yang penting karena jika minat Anda dalam mencoba menyelesaikan masalah, Anda harus memiliki latar belakang di bidangnya dan ide untuk memulai.

$P \neq NP$

Semoga berhasil. Masalahnya tampaknya sulit. :-)

$P$$NP$

Referensi klasik untuk kelengkapan NP adalah buku Garey dan Johnson (http://tinyurl.com/2w5yofs). Baik instruktif dan menyeluruh.

Secara pribadi, saya belajar dari Kleinberg Tardos (http://tinyurl.com/37dtyyl), karena Universitas saya menggunakannya.

Saya juga menyarankan untuk mengambil contoh masalah dan mencoba menyelesaikannya. Merupakan praktik yang baik untuk bereksperimen dengan masalah terbuka. Maksud saya percobaan, Anda dapat menulis program atau mengimplementasikan algoritma yang dikenal oleh orang lain dan memahami bagaimana mereka bekerja, di mana mereka gagal dll. Juga, Anda dapat menemukan beberapa teknik bukti. Ingat, mereka tidak akan memenjarakan Anda jika Anda belajar dan bekerja keras dalam hal ini dan tidak dapat menemukan solusi. Sebaliknya, tingkat kompetensi Anda dijamin meningkat.

Dalam kebanyakan kasus, masalah-masalah ini secara umum sulit untuk dipecahkan daripada contoh spesifik mereka . Baca tentang NFL untuk mendapatkan ide.

Dalam kasus saya, saya segera dimakamkan di bawah kumpulan ide dan konsep terkait. Ada pemrograman / coding tweak dan ada manuver teoritis. Sebagai contoh, jika Anda ingin menyelesaikan masalah misalnya menggunakan konsep Algoritma Genetika, Anda akan segera menemukan, GA sendiri adalah dunia yang luas untuk dijelajahi! Baru-baru ini saya mengetahui tentang Linkage Learning di GA / EA. Tidak tahu banyak tentang itu.

Selain itu, ketika Anda mencoba untuk membuat kode, Anda akan menemukan beberapa bahasa / alat pemrograman lebih baik / lebih mudah daripada yang lain. Saya tersesat dalam diskusi, mengapa Alex Stepenov berpikir OOP secara matematis salah dan apa kelebihan pemrograman fungsional. Saya tidak memiliki jejak tetapi saya ingat dengan jelas, pada awalnya saya mempelajari masalah NP-Complete / Hard.

Saya menyambut Anda, karena perjalanan ini meskipun penuh petualangan!

P, NP, dan NP-Completeness: The Basics of Complexity Theory oleh Oded Goldreich akan menjadi buku pengantar yang bagus.

Setelah konten pengantar, saya juga ingin merekomendasikan Pertanyaan P = NP dan Surat Hilang Gödel oleh Richard J. Lipton.

Saya merekomendasikan artikel ulasan yang sangat baik oleh Lance Fortnow, "Status Masalah P versus NP" , yang membahas beberapa pendekatan baru untuk masalah tersebut.

$P=?NP$$\mathcal{P}$$\mathcal{NP}$

Lance Fortnow baru-baru ini memperluas dan menerbitkan kolomnya yang sudah komprehensif dari CACM (disebutkan dalam jawaban MA lainnya) ke dalam buku tingkat ilmu pengetahuan populer, The Golden Ticket: P, NP, dan Search for the Impossible . itu diulas di New Yorker, "Masalah matematika yang paling mendalam" , oleh Nazaryan. ( halaman penerbit , Princeton University Press)