Apa dampak dari P = NP? [Tutup]

18

Saya sedang bersiap untuk ujian dan saya tidak dapat menemukan jawaban yang jelas atas pertanyaan: Apa dampak membuktikan bahwa PTIME = NPTIME. Saya memeriksa wikipedia dan hanya disebutkan bahwa itu akan memiliki "dampak mendalam pada matematika, AI, algoritma .." dll.

Adakah yang bisa memberi saya jawaban?

algorithms complexity latusaki
sumber
Ini sama sekali tidak ada hubungannya dengan pengembangan perangkat lunak. Saya menutup untuk sekarang tetapi meminta mod di Math.StackExchange jika mereka ingin saya memigrasikan ini untuk Anda.
maple_shaft

Jawaban:

22

Hal pertama yang terlintas dalam pikiran adalah bahwa keamanan kriptografi kunci publik saat ini tergantung pada ketidakmampuan untuk memecahkan masalah matematika yang ada di kelas kesulitan NP. Jika P = NP, segala sesuatu yang bergantung pada PKC (termasuk HTTPS, yang berarti seluruh infrastruktur e-commerce di seluruh dunia modern ) harus dikerjakan ulang!

Mason Wheeler
sumber
4
Ini akan memastikan bahwa ada algoritma yang berjalan dalam waktu polinomial. Maka hanya akan menjadi hitungan mundur untuk menemukan algoritma tersebut dan kemudian kaboom sehingga untuk berbicara.
Insinyur Dunia
7
Bukti akan melibatkan menemukan algoritma waktu polinomial untuk masalah NP-lengkap. Dan ketika Anda menemukan satu algoritma polinomial, Anda dapat menggunakannya untuk menyelesaikan semua masalah NP-lengkap lainnya dengan mengurangi masalah ke bentuk umum. Ini berarti bahwa bukti untuk P = NP dan algoritma yang menggunakannya akan muncul pada saat yang sama.
Oleksi
7
Tentu saja faktor yang konstan mungkin sangat besar untuk menjadikan ini hanya masalah teoretis ... untuk beberapa waktu.
quant_dev
17
Ketika kita menemukan algoritma seperti itu mungkin masih memiliki faktor konstan yang sangat tinggi atau memiliki tingkat yang luar biasa (n ^ 10.000 adalah polinomial, tetapi untuk banyak tujuan praktis itu jauh lebih buruk daripada kompleksitas eksponensial kecil). Tentu saja itu akan menjadi tanda peringatan bagi semua orang untuk menjauh dari metode lama, seperti kita pindah dari DES sebelum terbukti dapat dipecahkan, tetapi ekonomi dunia tidak akan segera runtuh. Pikirkan saja uang itu sendiri: semua orang pada akhirnya tahu bahwa uang itu tidak benar-benar berfungsi kecuali jika Anda mempercayainya, tetapi perdagangan global masih berfungsi dengan baik.
Kilian Foth
5
Kami mungkin akan menggunakan bantalan sekali pakai. Amazon dapat mengirimi Anda thumbdrive 1-Gig yang akan bekerja dengan situsnya dan menahan Anda selama sisa hidup Anda.
Macneil
18

Ini tercakup dalam Status Masalah P Versus NP . Pasti layak dibaca.

Beberapa poin penting dari artikel (dikutip dari bagian What If P = NP? ):

  • Kriptografi kunci publik menjadi tidak mungkin.
  • Karena semua masalah optimisasi NP-selesai menjadi mudah, semuanya akan jauh lebih efisien. Transportasi semua bentuk akan dijadwalkan secara optimal untuk memindahkan orang dan barang di sekitar lebih cepat dan lebih murah. Produsen dapat meningkatkan produksinya untuk meningkatkan kecepatan dan mengurangi limbah.
  • Belajar menjadi mudah dengan menggunakan prinsip Occam's razor — kami hanya menemukan program terkecil yang konsisten dengan data. Pengenalan visi yang nyaris sempurna, pemahaman bahasa dan terjemahan serta semua tugas pembelajaran lainnya menjadi sepele. Kami juga akan memiliki prediksi cuaca dan gempa bumi yang jauh lebih baik dan fenomena alam lainnya.
  • P = NP juga akan memiliki implikasi besar dalam matematika. Orang dapat menemukan bukti pendek, sepenuhnya logis untuk teorema tetapi bukti ini biasanya sangat panjang. Tapi kita bisa menggunakan prinsip Occam razor untuk mengenali dan memverifikasi bukti matematis seperti yang biasanya ditulis dalam jurnal. Kami kemudian dapat menemukan bukti dari teorema yang memiliki bukti panjang yang masuk akal mengatakan di bawah 100 halaman. Seseorang yang membuktikan P = NP akan pulang dari Clay Institute bukan dengan cek $ 1 juta tetapi dengan tujuh (sebenarnya enam sejak Poincaré Conjecture nampaknya diselesaikan).
vinaykola
sumber
2
Saya gagal melihat bagaimana P = NP menyiratkan kriptografi kunci publik tidak mungkin. Ini menunjukkan (tetapi tidak menyiratkan) bahwa implementasi saat ini tidak sesulit yang kita bayangkan. Tetapi seperti yang telah ditunjukkan orang lain, jika konstanta yang relevan dalam algoritma pengurangan waktu yang optimal sangat besar, maka P = NP tidak akan berdampak pada kriptografi kunci publik.
emory
Memberi +1 untuk poin ketiga - semua orang tahu bahwa P = NP akan memengaruhi crypto, tetapi untuk beberapa alasan Anda jarang mendengar tentang bagaimana hal itu akan memengaruhi setiap disiplin komputasi lainnya di planet ini.
BlueRaja - Danny Pflughoeft
@emory: Saya tidak akan berpura-pura menjadi ahli, tetapi pemahaman saya adalah bahwa jika algoritma seperti itu ditemukan, bahkan dengan konstanta yang cukup tinggi, kita harus benar-benar memikirkan kembali pendekatan kita. Juga, siapa yang mengatakan begitu suatu algoritma ditemukan, kita tidak dapat menemukan yang lain dengan konstanta yang lebih kecil? Satu algoritma akan membuka semua masalah NP-complete lainnya juga. Jadi efek langsungnya mungkin tidak besar, tetapi banyak pemikiran harus dimasukkan ke dalam mengubah semua sistem yang ada.
vinaykola
pertama kali saya mendengar tentang prinsip silet Occam. Hal-hal menarik ...
UmNyobe
@vinaykola membuktikan P = NP tidak berarti menemukan suatu algoritma. Tentu saja menemukan algoritma akan menjadi cara yang paling mudah (tetapi bukan satu-satunya) untuk membuktikan P = NP dan kemudian jika konstanta itu masuk akal, kita bisa masuk ke masalah yang Anda kemukakan.
emory
7

Kebanyakan masalah lengkap NP memiliki aplikasi kehidupan nyata yang "menarik". P=NPakan memiliki banyak konsekuensi:

  • Dimungkinkan untuk menyelesaikan masalah optimisasi yang tepat yang saat ini diperkirakan. Ini adalah kasus dari Masalah Salesman Perjalanan dan Masalah Penjadwalan Pekerjaan
  • Itu melanggar beberapa langkah-langkah keamanan yang didasarkan pada kenyataan bahwa waktu komputasi yang diperlukan sangat besar. Misalnya banyak skema enkripsi dan algoritma dalam kriptografi didasarkan pada faktorisasi angka, algoritma paling terkenal yang memiliki kompleksitas eksponensial. Algoritma ini akan menjadi tidak berguna jika algoritma polinom ditemukan.

Intinya adalah pada sifat dari masalah yang dikenal sebagai NP-complete. Ini bukan hanya masalah yang diciptakan oleh beberapa ilmuwan di lokasi terpencil untuk saling menghibur. Mereka dapat diekspresikan dalam istilah bisnis. Bahkan, beberapa pewawancara pekerjaan suka menyembunyikan masalah NP-lengkap dalam pertanyaan mereka untuk menguji kandidat.

UmNyobe
sumber
3
Sementara faktorisasi bilangan bulat adalah masalah yang sulit, perlu dicatat bahwa itu tidak diketahui sebagai NP-lengkap.
dan_waterworth
4
@dan_waterworth: Tidak diketahui apakah faktorisasi bilangan bulat NP-hard, tetapi diketahui bahwa itu ada dalam NP. [Seringkali orang mengatakan "NP-complete" ketika yang mereka maksudkan "dalam NP" atau "NP-hard". Di satu sisi, itu akan seperti seseorang yang mengatakan "kurang dari atau sama dengan" dalam situasi di mana "kurang dari" akan lebih tepat.]
Macneil
5

Kemungkinan-kemungkinan ini tercakup dalam Lima Dunia Impagliazzo .

Inilah beberapa poin takeaway:

  • Inteligensi buatan akan mampu membuat lompatan raksasa. Sebagai contoh, dengan "data pelatihan" yang cukup, sirkuit pendek untuk menghasilkan output yang benar dari input akan mewakili metode terjemahan terbaik. Secara khusus, akan menjadi sepele untuk memiliki pengenalan ucapan dan terjemahan bahasa yang sempurna. Mengambil ide ini lebih jauh, jika data pelatihan Anda adalah film pemenang Oscar, itu dapat menghasilkan lebih banyak film pemenang Oscar untuk Anda.

  • Algoritma yang diajarkan di sekolah akan sangat berbeda. Alih-alih mempelajari begitu banyak teknik algoritmik yang berbeda , kursus akan berfokus pada pengurangan masalah untuk verifikasi jawaban yang benar. Ini akan sangat menyederhanakan pemrograman.

  • Ekonomi akan menjadi jauh lebih efisien. Akan ada gangguan, termasuk mungkin pemindahan programmer. Praktik pemrograman itu sendiri akan lebih banyak tentang mengumpulkan data pelatihan dan lebih sedikit tentang menulis kode. Google akan memiliki sumber daya untuk unggul di dunia seperti itu.

  • Karena kriptografi kunci publik akan "keluar," Amazon perlu mengirimkan pad sekali pakai pada thumb drive untuk melakukan transaksi aman.

  • Bukti matematika dapat secara otomatis dihasilkan dan diverifikasi.

Secara keseluruhan, itu akan memperkenalkan singularitas teknologi; implikasi dari P = NP akan jauh jangkauannya. Juga, Lance Fortnow membahas hal ini dalam posting blog terpisah yang harus Anda baca.

Macneil
sumber
-1

Dampak membuktikan P = NP akan mencakup minat baru dalam menemukan algoritma reduksi. Orang-orang juga akan mencoba untuk menemukan batas bawah pada konstanta yang terkait dengan algoritma reduksi.

Membuktikan P = NP tidak akan sama pentingnya dengan klaim jawaban lain, karena itu bisa datang dalam bentuk bukti pengetahuan nol. Mengetahui P = NP tanpa mengetahui algoritma reduksi akan sedikit berbeda dari situasi saat ini.

Bayangkan jika seseorang membuktikan bahwa algoritma reduksi ada tetapi O (sqrt (n) + 2 ^ 4096).

emory
sumber
1
Sebenarnya, ada algoritma reduksi eksplisit yang ada di P jika dan hanya jika P = NP. Ini terdiri dalam iterasi atas semua program yang mungkin dan menjalankannya secara paralel sampai orang menemukan solusinya.
Arthur B
@ArthurB menarik. Dengan asumsi bahwa P = NP, berapakah urutan algoritma?
emory
Tidak diketahui, tetapi ini adalah urutan optimal. scholarpedia.org/article/Universal_search
Arthur B
1
@ ArthurB jadi jika P = NP dan algoritma reduksi adalah O (n ^ 99999999) apakah P = NP masih merupakan masalah besar?
emory