Apa yang akan menjadi implikasi dunia nyata dari bukti

Saya memiliki pemahaman tingkat tinggi tentang masalah dan saya mengerti bahwa jika itu benar-benar "terbukti" benar dengan solusi yang diberikan, itu akan membuka pintu untuk memecahkan berbagai masalah dalam bidang ilmu komputer.$P=NP$

Pertanyaan saya adalah, jika seseorang mempublikasikan bukti konstruktif tak terbantahkan , apa saja efek langsung yang akan kita lihat dari penemuan semacam itu? $P=NP$

Saya tidak meminta pendapat pendapat tentang bagaimana dunia akan terlihat dalam 5-10 tahun. Alih-alih, ini adalah pemahaman saya bahwa ini adalah masalah yang secara mendasar tidak dapat diselesaikan sehingga secara radikal dapat mengubah cara kita menghitung ... banyak hal (ya, ini adalah di mana ketidaktahuan saya menunjukkan ...) yang tidak dapat kita hitung dengan mudah hari ini .

Apa jenis efek yang hampir langsung akan bukti menyeluruh, akurat, dan konstruktif terhadap dunia praktis?$P=NP$

Orang-orang telah memberikan jawaban yang baik dengan asumsi bahwa dengan konstanta yang sangat besar. Saya akan bermain optimis dan menganggap bahwa kita menemukan bukti P = N P dengan konstanta kecil traktat. Mungkin tidak mungkin, tapi aku akan mencoba untuk memberikan beberapa wawasan ke dalam apa macam hal yang akan terjadi jika kita efisien bisa menyelesaikan semua N P masalah.$P=NP$$P=NP$$NP$

• Compiler: Beberapa program komputer akan menjadi sedikit lebih cepat, karena kompiler menggunakan pewarnaan grafik untuk alokasi register. Kami akan dapat mengalokasikan untuk sejumlah besar register dengan tepat. Kompiler yang ada menggunakan perkiraan solusi (seperti grafik chordal) akan mendapatkan output yang lebih baik, dan mereka yang menggunakan solusi pasti akan menjadi lebih cepat.

• Lokasi fasilitas: Bisnis akan dapat menemukan tempat yang optimal untuk menempatkan pabrik dan memasok depot untuk dikirimkan ke toko mereka, ketika mungkin ada ribuan toko dan pabrik. Kemungkinan tidak akan menjadi peningkatan besar atas perkiraan modern, tetapi akan mengurangi biaya.

• Membeli tiket pesawat: tiket pesawat aneh karena mereka tidak mengikuti persamaan segitiga. Terkadang lebih murah untuk terbang dari A -> B -> C daripada langsung dari A -> C, sesuatu yang tidak muncul saat memodelkan jarak. Akan mudah untuk membuat situs web yang menemukan urutan penerbangan termurah mutlak yang mengunjungi sejumlah kota dan mulai dan berakhir di kota asal Anda.

• Desain sirkuit: sirkuit listrik pada sebuah chip pada dasarnya adalah formula Boolean. Hal-hal seperti minimalisasi dapat dihitung secara efisien, sehingga perangkat keras kita akan menjadi sedikit lebih efisien.

• Penjadwalan: gila bahwa sekolah Anda menempatkan dua ujian Anda pada waktu yang sama? Jika sekolah Anda dapat berapa kali banyak yang mereka butuhkan sehingga tidak ada siswa yang memiliki konflik, atau diberi sejumlah slot waktu, minimalkan jumlah konflik.$P=NP$

Ini hanyalah sebuah contoh dari aplikasi praktis bahwa kita akan melihat apakah -completeness tidak penghalang. Saya yakin saya telah kehilangan banyak, tetapi jika konstruksi yang diberikan memiliki konstanta yang baik, implikasinya akan jauh jangkauannya.$NP$

Kami tidak perlu melihat efek apa pun. Misalkan seseorang menemukan algoritma yang memecahkan 3SAT pada variabel dalam 2 100 n operasi dasar. Anda tidak akan dapat menjalankan algoritme ini dalam keadaan apa pun, karena ini terlalu lama. Atau misalkan dia menemukan algoritma yang berjalan di operasi dasar n 100 . Kami hanya akan dapat menggunakannya pada instance 3SAT pada variabel tunggal, karena untuk lebih banyak variabel itu terlalu lama.$n$$2^{100} n$$n^{100}$

Di sisi lain, anggaplah P NP, dan bahkan hipotesis waktu eksponensial yang lebih kuat berlaku. Maka secara umum, 3SAT harus tidak dapat digunakan. Namun pemecah SAT tampaknya bekerja dengan baik pada masalah tertentu.$\neq$

Apa yang sedang terjadi disini? Ada beberapa masalah dengan pertanyaan P vs NP:

1. Ini hanya menyangkut kasus terburuk.
2. Itu hanya asimptotik.
3. Semua batas waktu polinom adalah sama.

Masalah-masalah ini meragukan relevansinya dengan dunia nyata. Sekarang dapat terjadi bahwa beberapa algoritma yang sangat cepat ditemukan untuk 3SAT, begitu cepat sehingga bahkan enkripsi simetris akan menjadi mudah pecah. Tetapi saya menganggap ini sangat tidak mungkin. Di sisi lain, itu sangat konsisten untuk P berbeda dari NP sementara memfaktorkan menjadi praktis; yang akan merusak skema enkripsi kunci publik tertentu. Ini adalah situasi yang kemungkinan akan berakibat, tetapi tidak terkait dengan pertanyaan P vs NP.

Pertanyaan P vs NP mungkin alami dari sudut pandang matematis, tetapi menurut saya relevansi praktisnya diragukan. Penelitian tentang pertanyaan, di sisi lain, mungkin atau mungkin tidak memiliki dampak praktis; tidak dibimbing oleh aspek ini.

Bacaan yang sangat bagus di sini adalah [1], di mana Impagliazzo mempertimbangkan lima kemungkinan "dunia" di mana hubungan antara kelas kompleksitas berbeda. Sebagai contoh, di dunia yang disebut Algorithmica (lihat Bagian 2.1), kita memiliki (atau beberapa "kesetaraan moral" lainnya berlaku, seperti N P ⊆ B P P ).$\sf P = NP$$\sf NP \subseteq BPP$

Di Algorithmica, hampir semua masalah optimasi akan sepele. Bahasa pemrograman bisa berupa bahasa di mana satu spesies memiliki properti yang diinginkan dalam kaitannya dengan input, alih-alih menentukan bagaimana perhitungan harus dilakukan. Komputer juga dapat menemukan bukti untuk teorema apa pun dalam waktu kira-kira panjang buktinya. (Pandangan ini sangat optimis tentu saja, dan tergantung pada algoritma yang efisien untuk beberapa masalah -Lengkap).$\sf NP$

[1] Russell Impagliazzo. Pandangan Pribadi tentang Kompleksitas Kasus Biasa. Konferensi Kompleksitas, 1995.

Bahkan tanpa P = NP, komputer saat ini sangat kuat.

• 12873891274647018937561708356916501047777612653914909670721635802187 dapat difaktorkan oleh satu komputer dalam waktu kurang dari satu detik.
• Untuk tugas-tugas yang lebih sulit seperti mensintesis tata letak listrik sebuah chip dari deskripsi fungsi yang lebih tinggi, atau mengoreksi foto-foto untuk mengimbangi artefak dari proses pembuatan, kelompok ratusan komputer bekerja sehari penuh untuk memungkinkan yang tidak mungkin.
• Komputer saat ini mampu membuktikan teorema matematika yang tidak dapat dibuktikan oleh manusia, seperti bahwa aljabar Robins adalah Boolean, atau bahwa konstanta tertentu yang diperkirakan tidak terikat ( Erd's Discrepancy Problem ) lebih besar dari 2.
• Program analisis kode sumber statis dapat mengidentifikasi kerentanan seperti bug Heartbleed .
• Alat penalaran otomatis seperti prover9 atau the-E-theorem-prover mampu membuktikan sebagian besar karakterisasi aljabar umum dari semigroup terbalik dan cincin yang sangat teratur tanpa bantuan eksplisit.

Sunting 22 Jan 2018 Saya tahu sekarang bagaimana saya seharusnya "menafsirkan" teks yang dikutip dalam contoh di bawah ini. Itu kesalahan saya sendiri, elemen terbalik harus unik . Ini adalah file input saya dari 22 Des 2014 ( addinvrig.in ) dan di sini adalah file input tetap dari hari ini ( addinvrigFixed.in ). Garis krusial adalah (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).Kekuatan alat penalaran otomatis sendiri masih menarik bagi saya, bahkan jika mereka tidak dapat menyelamatkan saya dari salah menafsirkan tulisan orang lain.

Menggunakan alat penalaran otomatis sangat berguna bagi saya, ketika saya menemukan teorema yang dikutip di mana saya tidak yakin bagaimana "menafsirkan" teks :

$x, y \in S$$(x \cdot y)' = x' \cdot y = x \cdot y'$$x' \cdot y' = x \cdot y$
$a \in aS \cap Sa$$a \in S$$S$

Saya mengadaptasi file input prover9 saya untuk teorema ini, dan segera ditunjukkan contoh-counter untuk teorema sebagaimana dikutip. Sedikit memodifikasi asumsi menghasilkan banyak teorema benar yang serupa, yang membuat kemungkinan bahwa Karvellas benar-benar menyatakan dan membuktikan teorema yang benar, yang hanya dikutip secara salah di sini. Googling untuk referensi teorema ini hanya muncul kertas lain yang mengutip Karvellas bahkan kurang akurat .

Ini adalah kumpulan hasil bantuan komputer yang luar biasa tidak lengkap untuk masalah khusus yang tidak bisa dipecahkan secara umum jika P! = NP. Mungkin koleksi ini menjelaskan kepada setidaknya beberapa pembaca bahwa kita semua cenderung meremehkan kekuatan komputer dalam domain ini. Banyak jawaban lain untuk pertanyaan ini tampaknya menunjukkan bahwa tidak akan ada konsekuensi besar jika komputer akan (sedikit) lebih baik dalam memecahkan masalah yang sulit diatasi. Tetapi komputer menjadi lebih baik dalam memecahkan masalah yang tidak dapat dipecahkan sepanjang waktu (karena cukup banyak waktu dan uang dihabiskan untuk mewujudkan hal ini), dan ini memiliki konsekuensi yang sangat nyata. Jika P = NP akan dibuktikan, maka mungkin kesadaran tentang apa yang sebenarnya dapat dilakukan komputer (bahkan hari ini) akan meningkat, dan lebih banyak orang akan menggunakan komputer untuk membantu mereka dengan tugas-tugas tersebut. (PS: Saya yakin P! = NP,

Ada banyak pendapat tentang implikasi dunia nyata P = NP. Seperti yang terlihat dalam tanggapan baik lainnya, umumnya ada 2 aliran pemikiran. Salah satunya adalah bahwa algoritma P-waktu mungkin sangat sulit atau tidak layak untuk benar-benar diterapkan karena "anomali tak terduga" yang terkait dengan abstraksi. misalnya:

• program mungkin terlalu "besar" untuk benar-benar kode
• mungkin ada konstanta yang sangat besar yang terlibat sehingga untuk semua contoh dalam jangkauan "perhitungan terestrial", mereka masih berjalan lama, yaitu efisiensi tidak "masuk" kecuali untuk kasus yang sangat besar. diketahui bahwa beberapa algoritma benar-benar cocok dengan kasus ini seperti yang baru-baru ini ditunjukkan oleh Knuth (pertanyaan 15)

Secara umum saya mencari lebih fokus pada algoritma yang bekerja cepat sehubungan dengan masalah yang ukurannya, n, layak. Sebagian besar literatur saat ini dikhususkan untuk algoritme yang asimtotik hebat, tetapi hanya membantu ketika n melebihi ukuran alam semesta.

Sebuah studi kasus terkenal dilakukan oleh Impagliazzo sebagaimana dikutip oleh J. dalam jawaban lain. Namun, esainya telah diekstrapolasi agak sementara. Berikut ini adalah referensi baru yang hebat dari seorang ahli yang mengisi pertanyaan ini dalam semacam skenario masa depan sci-fi, ch2 / p11. meringkas

Tiket emas: P, NP, dan pencarian yang mustahil oleh Lance Fortnow

• "Jika ternyata P = NP dan kami memiliki algoritma yang efisien untuk semua masalah NP, dunia akan berubah dengan cara yang akan membuat Internet tampak seperti catatan kaki dalam sejarah. Tidak hanya tidak mungkin untuk menggambarkan semua perubahan ini tetapi implikasi terbesar dari teknologi baru tidak mungkin untuk diprediksi. "

• Algoritma dengan cepat diimplementasikan pada komputer super. Boeing segera menandatangani kontrak untuk mendapatkan desain sayap yang lebih baik untuk pesawat baru yang memungkinkannya terbang dari London ke Sydney tanpa henti.

• Algoritma pencarian digunakan untuk menemukan algoritma baru yang lebih cepat, mengoptimalkan solusi P = NP asli. Berakhir dengan hasil 42 juta baris kode yang tidak dapat dipahami. Disebut "algoritma Urbana"

• Algoritma yang digunakan untuk menemukan perawatan kanker khusus / hampir sembuh untuk individu. menyembuhkan kanker, AIDS, diabetes tetapi pilek tetap menjadi misteri

• Algoritma super penjadwalan memungkinkan peramal untuk "membuat kemajuan luar biasa dalam prediksi cuaca, memungkinkan prediksi akurat suhu, angin, tutupan awan, dan curah hujan hampir setahun sebelumnya. Algoritma serupa sekarang menyelamatkan nyawa dengan memprediksi badai, tornado, badai secara akurat sehingga orang dapat siapkan atau evakuasi sesuai kebutuhan. "

• Pengenalan wajah yang sangat akurat

• Komputer dapat merekonstruksi model 3d pemandangan secara realtime dari sudut kamera yang berbeda

• Algoritma komputer mengontrol operasi kamera untuk acara olahraga (alih-alih dikendalikan manusia)

• Komentar dan ulangan otomatis dihasilkan oleh algoritme termasuk sudut dan statistik yang dipilih dengan baik, dan dihasilkan dalam bahasa apa pun secara realtime

• Bisbol fantasi / olahraga mengambil dimensi baru dengan simulasi yang sangat akurat

• Rasa resep makanan ditingkatkan oleh algoritma

• Algoritme dapat digunakan untuk "mempelajari apa saja, termasuk apa yang membuat seni yang baik, musik populer, dan kata-kata yang menggerakkan jiwa. Ingat bahwa P = NP berarti apa yang dapat kita uji, kita dapat menemukan. Jadi, sekali Anda memiliki algoritmik proses untuk mengenali kebesaran, Anda dapat menggunakan algoritma lagi untuk dengan cepat menemukan kebesaran itu. "

• Politisi menggunakan algoritma komputer untuk mengenali pidato hebat dan menghasilkan pidato yang sesuai dengan polanya. Pidato menjadi viral di internet.

• Orang-orang menghasilkan karya seni yang lengkap dari seni yang tidak lengkap / belum selesai misalnya simfoni. mereka menggunakan algoritma untuk menghasilkan catatan Beatles / Elvis baru. Seni, novel, drama, dan puisi baru misalnya komedi romantis dengan Humphrey Bogart / Julia Roberts.

• Amazon dapat membuat novel khusus untuk individu sesuai permintaan. NBC membuat serial televisi petualangan aksi langsung yang dibuat seluruhnya oleh komputer

• Simulasi virtual reality di video game memungkinkan tindakan apa pun dari para pemain alih-alih sekumpulan alur cerita yang mungkin.

• Penegakan hukum menggunakan algoritma sebagai "alat luar biasa dalam menyelesaikan kejahatan, tampaknya melakukan hal yang mustahil dalam melacak tersangka." Algoritma komputer dapat merekonstruksi wajah yang mungkin (untuk sketsa komposit) hanya menggunakan DNA. Polisi mencocokkan tersangka pembunuhan menggunakan pencarian besar-besaran dari basis data foto-foto SIM yang disejajarkan dengan sketsa yang dihasilkan (dari DNA).

Sayangnya tidak banyak yang dijelaskan Fortnow di atas didukung oleh literatur ilmiah yang sebenarnya kecuali mungkin ekstrapolasi imajinatif dari dunia Impagliazzos. akan diperlukan jauh lebih banyak untuk membedah poin demi poin ini, tetapi untuk meringkas, semuanya tampak menghibur tetapi pemikiran yang fantastis / angan-angan (atau mungkin itu adalah poin terselubungnya). Sebenarnya ada prinsip-prinsip ilmiah yang bertentangan dengan banyak item. Dan perhatikan Fortnow adalah penggemar olahraga sehingga mengembangkan metafora yang luas di daerah itu, tetapi mungkinkah ini lebih merupakan indikasi manusia berpikir dalam alur ?

Misalnya "efek kupu-kupu" diketahui menyiratkan bahwa prediksi cuaca akurat melewati cakrawala beberapa hari adalah tidak mungkin karena "ketergantungan sensitif pada kondisi awal" (dan Fortnow kemudian mengakui di blognya untuk mengulangi kritik tentang hal ini titik). Juga, ada banyak bukti bahwa komputer gagal pada tugas yang sangat manusiawi-subyektif seperti menghasilkan atau mengidentifikasi seni yang berpengaruh (tugas yang bahkan manusia ahli tidak berhasil secara konsisten).

Sebenarnya seluruh pertanyaan sedang ditanggapi dengan kontrafaktual atau premis yang salah . Perhatikan bahwa sebagian besar ilmuwan ahli yang disurvei berpikir / percaya, meskipun sejauh ini tidak ada bukti yang tidak dapat disangkal, P ≠ NP. dan adalah wajar untuk membandingkannya dengan hukum / batasan / batasan lain yang diketahui seperti termodinamika (mis. ketidakmungkinan gerak abadi / energi bebas ) dan statistik, misalnya "teorema makan siang gratis" .

Jadi intinya adalah bahwa mungkin bahkan ilmuwan ahli tidak dapat memprediksi hasil P = NP. Jadi mungkin jawaban terbaik untuk saat ini adalah mengakui bahwa manusia tidak memiliki jawaban yang baik saat ini.

P vs NP, secara teknis vs moral

$O(n^2)$$O(n^{\lg^* n})$$2^{65536}+2^{1024}n^{256}$$O(n^{\lg n})$

Jadi apa yang terjadi jika P = NP benar secara moral ?

$Q$$Q$benar maka semua masalah ini bisa diselesaikan dengan sangat cepat. Sebagai contoh, Anda dapat mempelajari bobot terbaik untuk model pembelajaran mesin yang sangat rumit. Anda dapat memutus protokol enkripsi.

$\neq$

$\neq$

$\neq$

Bahkan jika P$\neq$

$\neq$

Jika Anda tahu Anda ingin menyelesaikan masalah NP-complete bukan pada input umum tetapi pada input dengan properti tertentu Anda tidak perlu peduli dengan masalah umum. Anda hanya perlu menyelesaikan masalah yang lebih sederhana. Sayangnya seringkali tidak mudah untuk menentukan input apa yang Anda sukai dalam praktiknya.

$\neq$

Apa jenis efek yang hampir langsung akan bukti menyeluruh, akurat dari P = NP, dengan solusi yang diberikan, pada dunia praktis?

Mungkin ada banyak hal besar yang akan terjadi, tetapi tidak ada yang peduli.

Masalahnya adalah bahwa fondasi (hampir) semua enkripsi modern didasarkan pada asumsi bahwa P tidak sama dengan NP. Enkripsi yang melindungi kata sandi Anda saat masuk melalui internet, dan saat disimpan dalam database. Enkripsi yang melindungi data kartu kredit saat berjalan di internet ... Enkripsi yang melindungi miliaran transaksi keuangan harian yang mengikat ekonomi global kita menjadi organisme raksasa.

Kasus terbaik, P = NP berarti berhenti. Orang-orang kembali menggunakan uang tunai dan bank mencoba untuk mencatat penarikan tunai ini pada beberapa media yang terputus karena transaksi ke kantor pusat tidak lagi dapat dipercaya. Ini berlangsung selama mungkin beberapa bulan sampai enkripsi yang lebih baik diimplementasikan secara global. Kasus terbaik.

Kasus terburuk, P = NP berarti seseorang menghancurkan dunia. Mata uang dibangun berdasarkan konsep kepercayaan. Anda menghargai satu dolar, karena Anda percaya bahwa tetangga Anda akan memberi Anda barang atau jasa bernilai satu dolar untuk itu. Anda menghargai komputer Anda dengan mengatakan Anda memiliki 500 dolar di bank, karena Anda dapat menggesek kartu Anda dan mendapatkan barang dan jasa senilai 500 dolar ...

Bagaimana jika Anda tidak percaya itu? Jika P = NP, seseorang dapat meniru berbagai bank, pemerintah, orang - dan secara efektif mengacak jumlah mata uang di setiap akun.Hapus mata uang di setiap akun. Tentu, berbagai bank memiliki cadangan untuk memperhitungkannya, tetapi berapa lama enkripsi mereka telah rusak? Transaksi mana yang baik, dan mana yang ditiru? Tidak mungkin tahu.

Setelah kepercayaan itu rusak, kekacauan terjadi. Setiap manfaat dari dapat berurusan dengan Masalah Salesman Perjalanan (misalnya) diabaikan karena orang berjuang untuk memberi makan diri mereka sendiri.

Realitas kemungkinan ada di antara keduanya, tetapi mudah-mudahan ini melukiskan gambaran yang cukup besar tentang betapa pentingnya masalah ini.

Penurunan besar dalam biaya peralatan, listrik, dan pendekatan cloud akan terjadi. Banyak hal yang sedang dihitung dengan kekuatan kasar sekarang, atau perkiraan yang masih menggunakan beberapa kekuatan kasar. Kami tidak lagi akan melakukan semua perhitungan brute force yang lumpuh besar-besaran itu.

Itu sama sekali bukan satu-satunya penggunaan komputasi awan, tetapi itu masih akan menjadi faktor nyata dalam penggunaan energi, pemrosesan cloud, dll. Hanya penghematan energi yang dapat terlihat pada jejak karbon kita.

AI juga akan menjadi jauh lebih baik. Kami akhirnya mungkin memiliki komputer yang bisa menjadi pemain GO terbaik, dan kalkulator grafik Anda akan mengalahkan Anda saat catur.

$\ne$ NP dan menemukan solusi di mana mereka kritis (seperti solusi perkiraan).

Dan dugaan yang dibantah tidak berarti bahwa semua masalah kegunaan praktis akan diselesaikan dalam satu jentikan jari. Pertama, mereka masih bisa lebih sulit daripada NP.