Membuktikan P = NP tanpa pernyataan matematis / program komputer

Ini adalah posting pertama saya setelah menjadi pengguna pasif untuk beberapa waktu sekarang. Saya ingin mengajukan beberapa pertanyaan jika saya bisa. Saya bukan ahli matematika tetapi pertanyaan saya berhubungan dengan bidang matematika / ilmu komputer. Secara khusus, masalah P vs NP. Saya sadar bahwa ini adalah masalah yang belum dapat diselesaikan oleh para profesional elit ...

Apapun, saya ingin bertanya:

Jika seseorang yang bukan ahli matematika atau seorang programmer datang dengan diagram alur atau serangkaian langkah-langkah yang ditulis dalam bahasa Inggris dasar yang diduga memberikan solusi untuk salah satu masalah P vs NP, apakah itu akan dianggap sebagai 'membuktikan' bahwa P = NP .. untuk mengklaim hadiah Clays Institute :)? Atau apakah suatu keharusan bagi seseorang untuk menulis solusi sebagai bukti matematika / program komputer?

Terima kasih.

complexity-theory p-vs-np Raphael
sumber

Lihat koleksi ini: win.tue.nl/~gwoegi/P-versus-NP.htm . Anda tidak ingin menjadi salah satu dari mereka.

Yuval Filmus

ada satu kemungkinan preseden "lemah" untuk ini. Godels thm dan diagonalisasi mungkin secara longgar didasarkan pada paradoks Richards yang berasal dari karya sastra. tetapi perhatikan bahwa dibutuhkan ahli matematika yang sangat canggih untuk mengubahnya menjadi pernyataan / sifat matematika yang sah.

vzn

@vzn: halaman Wikipedia yang Anda tautkan ke tanggal Richard's Paradox ke 1905; tanggal diagonalisasi kembali ke tahun 1891. Jadi Paradox Richard kemungkinan didasarkan pada diagonalisasi, bukan sebaliknya.

Niel de Beaudrap

@NieldeBeaudrap, vzn: Komentar Anda berubah menjadi percakapan jadi saya memindahkan mereka untuk mengobrol , silakan lanjutkan di sana.

Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

"Tidak", Anda dapat menggunakan "bahasa Inggris dasar".

Jika Anda berhasil, Anda akan membuat bukti konstruktif . Bukti dalam matematika sering merupakan campuran dari "bahasa Inggris dasar" seperti yang Anda sebut dan rumus matematika, tetapi mereka tidak perlu mengandung salah satu untuk menjadi bukti yang valid.

Misalkan Anda memiliki diagram alur seperti itu, apa yang perlu Anda buktikan — yaitu berdebat — adalah, bahwa algoritma Anda berfungsi untuk setiap instance masalah. Cara Anda melakukannya sepenuhnya terserah Anda, selama buktinya tidak ambigu dan semua tempat yang Anda nyatakan telah terbukti benar.

Setelah melakukan itu, Anda memiliki bukti matematika di tangan Anda. Jadi sungguh, saya seharusnya mengatakan " Ya " di awal, Anda memang membutuhkan bukti matematika .

hantu0m
sumber

Jangan beri siapa pun harapan palsu di sini. Sangat tidak mungkin bahwa orang awam dapat menyelesaikan

, atau bahwa solusinya dapat diekspresikan dalam "bahasa Inggris biasa". Ada hal-hal yang lebih baik untuk dilakukan oleh orang awam daripada mencoba memecahkan masalah matematika yang paling sulit.

P

$P$

N P

$NP$

Andrej Bauer

@AndrejBauer Tentu, saya tidak bermaksud mengatakan bahwa itu mungkin. Saya berasumsi bahwa Anda akan menyukai jawaban yang mirip dengan Niel lebih baik. Tetapi sementara itu menempatkan hal-hal ke dalam perspektif dengan baik, itu tidak benar-benar menjawab pertanyaan yang diajukan.

phant0m

Saya tahu Anda tidak bermaksud mengatakan hal seperti itu. Saya hanya ingin meletakkan peringatan eksplisit, jangan sampai jurnalis atau seseorang membaca ini dan berpikir

vs.

akan diselesaikan oleh seorang kritikus sastra.

P

$P$

N P

$NP$

Andrej Bauer

@ phant0m: Saya ingin tahu. Apakah paragraf pertama saya tidak menjawab pertanyaan yang sebenarnya?

Niel de Beaudrap

@NieldeBeaudrap Tentu, itu memang mengatasinya, tapi sepertinya kesimpulannya perlu disimpulkan. Sidenote: Seseorang juga dapat menafsirkan "Indeed"kalimat sebagai memberikan penjelasan tentang bukti dalam kata-kata, tetapi kalimat itu sendiri tidak akan menjadi bukti. Juga, mesin turing itu sendiri bukan merupakan bukti, kecuali bukti kebenaran diberikan. Juga, itu menyiratkan bahwa penyajian TM di atas diagram alur secara inheren lebih unggul sebagai "bukti", bahkan ketika itu bukan.

phant0m

Mesin Turing, harus diingat, adalah semacam bagan alur. Begitu juga dengan struktur program komputer pada umumnya. Jadi mengubah "diagram alur" menjadi jawaban formal untuk masalah itu seharusnya cukup mudah, jika itu benar-benar berhasil. Memang, jika seseorang mulai dengan jawaban yang sangat formal untuk P versus NP , sebagian besar ilmuwan komputer akan mencoba menemukan formulasi yang sedekat mungkin dengan deskripsi bahasa Inggris sederhana untuk mendapatkan pemahaman yang kuat tentang solusi sebagai bisa jadi.

Tetapi ada masalah mendasar dengan jenis pertanyaan yang Anda tanyakan. Apa artinya bagi seseorang yang dapat memecahkan P versus NP - dan dengan menunjukkan bahwa mereka setara, tidak kurang - untuk tidak benar-benar menjadi ilmuwan komputer atau ahli matematika? Mungkin mereka tidak dipekerjakan secara profesional sebagai ilmuwan komputer atau ahli matematika, tetapi ini tidak penting jika mereka memiliki keterampilan untuk memecahkan apa yang digambarkan oleh beberapa orang (Scott Aaronson, misalnya) sebagai masalah matematika paling penting yang pernah kita pertimbangkan. Jika seseorang memiliki pelatihan (atau bahkan otodidak) untuk berhasil mengatasi masalah, dan juga untuk mengkomunikasikan solusi dengan jelas kepada orang lain dengan mengidentifikasi sub-rutin utama dan peran mereka dalam menyelesaikan mis SAT atau HAMPATH, kemudian apakah mereka bekerja atau bahkan memiliki gelar adalah detail yang tidak relevan; namun mereka dalam hal itu ahli matematika atau ilmuwan komputer. Lebih baik lagi jika mereka dapat menggambarkan bagaimana solusi mereka mengatasi hambatan klasik seperti hasil oracle, seperti ramalan A yang P ^A ≠ NP ^A (atau sebaliknya) dengan menunjukkan secara spesifik jenis struktur dalam masalah yang digunakan algoritma, yang mana tidak akan dapat diakses dalam model oracle. Masalahnya, bagaimanapun, adalah bahwa kebanyakan orang yang bermimpi memecahkan P versus NP sebagai amatir atau orang luartampaknya kurang memiliki keterampilan komunikasi untuk benar-benar menggambarkan pekerjaan mereka secara memadai, atau (karena tidak cukup membaca) mereka tidak mengetahui hasil yang akan membuat pendekatan mereka untuk memecahkan masalah terkutuk sejak awal.

Seperti halnya semua mimpi kemuliaan hari ini, ada masalah mendasar dengan fantasi menjadi orang yang menyelesaikan P versus NP . Masalahnya adalah itu hampir mustahil. Sebenarnya bukan tidak mungkin, ingatlah Anda, atau setidaknya tidak selalu mustahil; hampir saja. Sebagai seseorang yang cerdas dengan ambisi, adalah mungkin bagi seseorang untuk melupakan fakta bahwa ada banyak orang cerdas lainnya: banyak dari mereka juga telah memikirkan masalah tersebut; dan banyak di antaranya lebih terang dari diri sendiri, bahkan oleh beberapa perintah besar. Dan bahwa ada orang-orang yang cemerlang selama masalahnya ada; namun tetap belum terpecahkan. Ya, pada prinsipnya mungkin bahwa semua orang berpikir tentang hal itu dengan cara yang salah, dan telah selama puluhan tahun. Tapi apakah itubenar - benar sangat mungkin? Tidak seorang pun harus mengharapkan diri mereka menjadi satu-satunya orang yang dapat menemukan satu kesalahan tanda yang dibuat orang lain, karena jika semua orang membuat kesalahan itu maka pasti ada sesuatu tentang masalah yang akan membuat seseorang membuat kesalahan yang sama. Atau - dalam hal yang lebih mungkin bahwa alasan mengapa masalah tetap tidak terpecahkan tidakbahwa orang terus membuat kesalahan sederhana atau belum memikirkan satu trik sederhana yang melarutkan semuanya - apa yang membuat masalah menjadi sulit pada dasarnya adalah kesulitan obyektif dari masalah, dan tidak ada langkah-langkah menari yang cerdas akan memungkinkan seseorang untuk melenggang dengan anggun. melewati semua rintangan; bahwa apa yang diperlukan adalah pendekatan yang bukan hanya novel, tetapi cukup mendalam, mengidentifikasi struktur halus bahwa ada alasan bagus untuk tidak ada yang melihat sebelumnya. Jenis struktur yang paling mungkin dikenali dengan berpikir terus menerus tentang masalah selama bertahun-tahun.

Jika Anda ingin realistis tentang apa yang diperlukan untuk menyelesaikan masalah P versus NP , Anda dapat membandingkannya dengan terobosan yang sama terkenalnya dalam beberapa dekade terakhir, seperti bukti teorema empat warna, Teorema Terakhir Fermat, atau Dugaan Poincaré. Mereka mungkin memiliki bukti yang lebih sederhana suatu hari nanti, tetapi bukti asli membawa Anda jauh ke hutan belantara untuk membawa Anda ke akhir (atau dalam kasus teorema Empat Warna, rute sangat panjang dan berulang-ulang). Tidak ada alasan khusus untuk mencurigai bahwa P versus NP akan berbeda; sehingga jika pada akhirnya memang demikiandiselesaikan oleh seorang amatir, kemungkinan sangat kuat bahwa itu akan dilakukan oleh seseorang dengan latar belakang pengetahuan yang sama dan kesadaran teknik seseorang yang terlatih secara akademis. Setiap amatir realistis yang bermimpi memecahkan P versus NP akan melakukannya dengan baik untuk diingat.

Niel de Beaudrap
sumber

Sementara semua yang Anda katakan itu benar, saya khawatir pola pikir ini (yang telah menjadi lazim di lapangan, mungkin sebagai mekanisme perlindungan) mungkin akan membuat orang jenius yang belajar sendiri bisa menyelesaikan masalah hari ini. Saya pikir pesan yang lebih bermanfaat adalah: pergi dan dapatkan pelatihan sebanyak yang Anda butuhkan untuk meyakinkan seorang profesional, pertama-tama untuk membaca karya Anda dan kemudian validitasnya. Mungkin butuh bertahun-tahun, tapi itulah caranya.

Raphael

@ Raphael: Saya pikir sebenarnya mentalitas saya sudah disesuaikan dengan baik bahkan untuk kemungkinan jenius yang belajar sendiri. Pesan saya kepada genius yang belajar sendiri adalah ini: di satu sisi, tidak menjadi akademis tidak berarti Anda bukan ahli matematika --- dan bahwa saya akan menilai jawaban berdasarkan kualitasnya. Jadi, tanggung jawabnya adalah pada kejeniusan yang belajar sendiri untuk memastikan bahwa jawabannya memiliki kualitas, dan untuk waspada terhadap perangkap yang sering menjadi mangsa para amatir.

Niel de Beaudrap

Saya takut bahwa pola pikir ini ... mungkin akan mencegah kejeniusan otodidak yang mungkin memecahkan masalah hari ini. - Bagus Jenius otodidak Anda harus diingatkan bahwa bilah sangat tinggi dan lusinan (ratusan?) Genius otodidak lainnya telah mencoba dan gagal mencapainya.

JeffE

"Teorema Terakhir Fermat, atau dugaan Poincaré. Mereka mungkin memiliki bukti yang lebih sederhana suatu hari nanti, tetapi bukti asli membawa Anda jauh ke hutan belantara untuk membawa Anda ke akhir (atau dalam kasus teorema Empat Warna, rute sangat panjang dan berulang) ". ini adalah ekspektasi yang adil / masuk akal oleh beberapa tetapi di sisi lain, tidak seperti keingintahuan teoritis sewenang-wenang seperti FLT dan 4CT, sebuah kasus dapat dibuat sebagai bukti P vs NP mungkin menghasilkan alat (mendasar) untuk pemisahan kelas kompleksitas lainnya dan teori kompleksitas pada umumnya , atau bahkan bisa menjadi batu rosetta atau tautan yang hilang untuk kemajuan selanjutnya ..

vzn

@ vz: Saya tidak begitu yakin apa yang Anda maksud dengan perbedaan itu. Hanya karena P versus NP penting, tidak membuatnya lebih mungkin bahwa ada menemukan solusi sederhana yang mungkin ditemukan oleh seorang amatir yang pintar tetapi belum tahu.

Niel de Beaudrap

-5

Bukti bahwa P = NP mungkin diterima oleh jurnal matematika, tetapi itu tidak akan pernah diterima oleh para profesional elit. Alasannya adalah bahwa mereka tahu P! = NP (setidaknya untuk semua tujuan praktis). Mereka juga tahu bahwa sulit untuk membuktikan ini, jadi bahkan sebuah bukti bahwa P! = NP akan diterima dengan jumlah skeptisisme yang sehat oleh para profesional elit.

Para profesional elit memiliki alasan yang lebih rumit daripada banyak pikiran cerdas yang mencoba dan gagal membangun algoritma polinomial untuk NP atau membuktikan N! = NP. Namun, mereka secara wajar berharap bahwa argumen ini harus menjadi yang paling meyakinkan bagi orang awam. Mereka mungkin benar bahwa referensi untuk hambatan yang terkait dengan bukti relativizing, bukti alami atau bukti algebrizing jarang meyakinkan untuk non-ahli. Jika terlalu banyak "amatir" mencoba menyelesaikan P vs NP dengan cara tertentu (misalnya dengan resolusi logis, atau dengan menguranginya menjadi masalah pemrograman linier), maka seseorang akan mengalami rasa sakit (ini kadang-kadang membutuhkan waktu bertahun-tahun) untuk membuktikan bahwa sudut serangan spesifik ini kemungkinan besar akan gagal.

Sunting Saya senang bahwa jawaban ini terus menarik umpan balik (negatif). Karena itu, izinkan saya mengganti bagian kedua dari jawaban (yang tampaknya tidak terkait dengan umpan balik, tetapi dapat mengalihkan perhatian dari poin utama) dengan kutipan berikut dari Truth vs Proof :

Kita bisa tetap agnostik, mengatakan bahwa kita tidak tahu, tetapi mungkin ada terlalu banyak skeptisisme dalam sains. Sebagai contoh, Scott Aaronson pernah mengklaim bahwa dalam ilmu lain P! = NP sekarang akan dinyatakan sebagai hukum alam. Saya cenderung setuju. Bagaimanapun, kami berusaha mengungkap kebenaran tentang sifat perhitungan dan pencarian ini tidak akan berjalan lebih cepat jika kami bersikeras membuang semua bukti yang tidak dalam bentuk bukti matematika dari prinsip pertama.

Perubahan ini tidak dimaksudkan untuk mengurangi jumlah umpan balik, tetapi untuk membuatnya sangat jelas bahwa jawaban ini serius tentang fakta bahwa para ahli "tahu bahwa P! = NP", meskipun demikian mereka tidak dapat membuktikannya.

23 Nov 2013 Terima kasih sekali lagi untuk semua umpan baliknya. Sebagai catatan, jawabannya sekarang memiliki 7 downvotes, 1 upvote dan 14 komentar (8 oleh saya). Karena jumlah komentar, referensi menarik dan justifikasi yang diberikan dalam komentar disembunyikan, jadi saya memutuskan untuk menambahkan beberapa di sini:

Sebagaimana Gödel sendiri menulis kepada von Neumann, jika P = NP benar "untuk semua tujuan praktis", maka teorema ketidaklengkapannya hanya akan benar dalam teori, tetapi secara efektif salah dalam praktik.
Dalam makalahnya tahun 1971, Stephen Cook ... tidak dapat menghasilkan contoh tandingan untuk prosedur Davis-Putnam (diselesaikan oleh Haken 1985). Saat ini, banyak teknik, hasil dan contoh tandingan tersedia untuk "menyangkal" pemecah NP yang efisien. Juga P = NP bertentangan dengan "hukum kekekalan", "korespondensi kualitatif infinititas <-> kuantitatif", ...
Dahulu kala, Scott Aaronson menulis komentar ini :

anonim: Anda mengklaim (sebagai fakta!) bahwa 3SAT adalah bahasa dalam NP yang tidak dapat dihitung dalam waktu polinomial. Tetapi Anda tidak dapat membuktikannya. Apakah itu metode ilmiah Anda? Iya. Sebagai orang yang sangat percaya pada sains dan akal, saya berusaha untuk membedakan dengan jelas antara apa yang dapat saya buktikan dan apa yang saya tahu benar.
Scott terkenal karena mencoba menunjukkan apa artinya bahwa dia "tahu" sesuatu, misalnya dengan bertaruh $ 200.000: scottaaronson.com/blog/?p=458

Thomas Klimpel
sumber

Amatir telah menghasilkan banyak bukti P = NP dan juga P

\neq

$\neq$ NP. Karena alasan itu, "profesional elit" tidak mungkin mempertimbangkan secara serius upaya para amatir. Namun, jika bukti benar, itu akan diterima oleh "profesional elit". Hasilnya mungkin tidak relevan dengan praktisi dunia nyata (memang, saya pikir itu akan terjadi), tetapi para ilmuwan komputer teoretis "profesional" akan peduli.

Yuval Filmus

Tidak ada yang "tahu" bahwa P! = NP. Para ahli mungkin sangat mempercayainya, tetapi tidak ada ahli yang mengetahuinya (kecuali seseorang memiliki bukti dan menyimpannya untuk dirinya sendiri). Adalah mungkin, meskipun tidak mungkin, bahwa P = NP benar. Sebagai catatan tambahan, setiap orang (terutama ilmuwan) harus terbuka untuk segalanya, kecuali jika terbukti sebaliknya. Dalam hal ini setiap ilmuwan, betapapun besarnya keyakinannya bahwa P! = NP, harus menerima bahwa ada kemungkinan yang dimiliki P = NP.

George

Dalam matematika, masalah dengan mengabaikan bukti dan melanjutkan secara membabi buta adalah bahwa Anda dapat menganggap sesuatu yang salah. Ini akan membuat pencarian berjalan lebih lambat. Ilmu fisika tidak memiliki masalah ini (kecuali untuk kasus-kasus seperti gravitasi quantum / teori string) karena mereka harus setuju dengan eksperimen.

Peter Shor

@ThomasKlimpel: Saya ingat memposting komentar itu, tetapi tidak di mana. Mengingat bahwa siapa pun yang saya tanggapi (Anda?) Hanya menggunakan dia sebagai otoritas untuk berdebat tentang kebenaran Platonisme matematika, sedangkan saya setelah beberapa pertimbangan sampai pada posisi formalis, fakta bahwa Godel memiliki pendapat berbeda tanpa lebih jauh elaborasi memang tidak relevan. Argumen teknis tidak dimenangkan seperti pertandingan tenis, dengan sanggahan cepat. Demikian pula, jawaban yang meyakinkan dinilai tidak hanya oleh keputusan mereka (meskipun itu membantu) atau oleh otoritas, tetapi oleh kemampuan teknis mereka.

Niel de Beaudrap

@ThomasKlimpel Dalam ilmu lain, kami akan melakukan pengamatan untuk mendukung hipotesis. Dalam kasus P

\neq

$\neq$ NP, satu-satunya bukti yang kami miliki adalah kurangnya bukti (yaitu fakta bahwa tidak ada yang mampu membuat algoritma waktu polinomial untuk masalah NP-hard). Saya tidak berpikir ilmu lain akan menggunakan kurangnya pengamatan sebagai sarana untuk "membuktikan" sesuatu; Jika Anda belum pernah melihat apel terlepas dari pohonnya, bagaimana Anda bisa mengklaim apel itu akan jatuh?

Raphael