Masalah P-NP adalah salah satu masalah yang paling mencabar dalam matematik, bertanya sama ada terdapat cara cepat untuk mencari jawapan yang betul untuk masalah yang diberikan. Jika diselesaikan, ia boleh merevolusikan cara kami menyelesaikan masalah pengoptimuman dalam industri yang pelbagai seperti penjadualan pesawat dan reka bentuk semikonduktor.

Seorang pencuri memasuki kedai barang kemas, melihat sekeliling, dan merenung sejenak. "Saya ingin mengambil semua barang kemas, tetapi malangnya, terdapat had untuk berapa banyak berat beg saya boleh menampung. Permata apakah yang perlu saya isi beg itu untuk mendapatkan wang paling banyak?” Terdapat terlalu banyak kemungkinan kombinasi permata dalam beg untuk mengira nilainya. Jika terlalu memakan masa untuk mengira dengan tangan, anda boleh memikirkan tentang menggunakan komputer dan perisian yang paling canggih dengan algoritma terbaik. Malangnya, tiada algoritma yang wujud pada masa ini untuk menyelesaikan masalah ini dengan cepat. Walaupun dengan komputer yang paling berkuasa, ia akan mengambil masa beribu-ribu tahun atau lebih. Sebab masalah ini, yang dipanggil "masalah ransel," begitu sukar kerana ia serupa dengan masalah P-NP, satu cabaran matematik yang hanya 53% ahli matematik percaya akan diselesaikan sebelum 2100.
Masalah P-NP adalah salah satu daripada tujuh cabaran matematik teratas dunia. Institut Matematik Tanah Liat di AS telah menyenaraikan tujuh masalah matematik yang belum diselesaikan untuk abad ke-21 dan menawarkan hadiah $1 juta untuk setiap satu. Hanya Konjektur Poincaré telah terbukti, tetapi enam yang lain, termasuk masalah P-NP, masih tidak dapat diselesaikan dan dicabar oleh ramai ahli matematik. Banyak masalah pengoptimuman dalam pelbagai bidang masyarakat, termasuk contoh pencuri, adalah "masalah sukar" dengan kerumitan pengiraan yang tinggi. Masalah P-NP adalah untuk membuktikan sama ada terdapat cara mudah untuk menyelesaikan "masalah sukar" ini.

Apakah Kerumitan Pengiraan?

Kerumitan pengiraan ialah ukuran objektif betapa sukarnya masalah yang kita cuba selesaikan. Dalam konteks ini, kekerasan tidak bermakna tiada penyelesaian kepada masalah, sebaliknya tiada algoritma yang boleh menyelesaikan masalah dengan cepat.
Berikut adalah contoh mudah. Terdapat 100 bola dengan nombor rawak yang berbeza ditulis padanya.

– Masalah 1: Apakah nilai maksimum nombor yang ditulis pada bola?
– Masalah 2: Adakah terdapat satu set bola sehingga jumlah nombor yang ditulis pada bola itu ialah 100?

Untuk Masalah 1, jika anda mengeluarkan satu bola dan menggantikannya apabila ia mempunyai nombor yang lebih besar daripada yang anda pegang, nombor yang anda terima adalah maksimum, yang bermaksud anda perlu membuat 99 perbandingan secara keseluruhan. Sebagai perbandingan, untuk Masalah 2, kita perlu menyemak sama ada terdapat set yang berjumlah 100 untuk setiap kombinasi yang boleh dibuat dengan 100 bola, yang bermaksud bahawa dalam kes yang paling teruk, kita perlu melakukan kira-kira 2 hingga kuasa ke-100 ( * jumlah bilangan subset) pengiraan. Walaupun dengan mengandaikan superkomputer melakukan operasi kuadrilion sesaat, ini akan mengambil masa yang tidak dapat dibayangkan, kira-kira 23 kuadrilion tahun.
Algoritma dipanggil algoritma masa polinomial jika, apabila bilangan bola (N) bertambah, bilangan operasi (N-1) tidak melebihi fungsi polinomial bilangan bola, seperti dalam penyelesaian Masalah 1. kewujudan algoritma sedemikian boleh menjadi perbezaan antara masalah mudah dan masalah sukar.

P=NP?

Perhatikan bahawa mencari jawapan kepada masalah sukar 2, yang tiada algoritma masa polinomial wujud, memerlukan jumlah pengiraan yang besar, tetapi mengesahkan bahawa jawapan itu betul adalah sangat mudah. Memandangkan satu set bola, ia perlu mengambil masa kurang daripada 10 saat untuk mengesahkan bahawa jumlah nombor yang ditulis ialah 100. Dalam erti kata lain, hanya kerana masalah mudah dikira tidak bermakna terdapat cara mudah untuk menyelesaikannya . Sama ada terdapat cara mudah untuk menyelesaikannya dan ahli matematik masih belum menemuinya, atau sama ada tiada cara mudah untuk menyelesaikannya pada mulanya, masih perlu dilihat. Ini adalah masalah P-NP.
Set P ialah set masalah mudah yang boleh dijawab dalam masa polinomial, seperti Masalah 1, dan set NP ialah set masalah yang boleh disemak untuk ketepatan dalam masa polinomial. Masalah P-NP ialah masalah untuk membuktikan sama ada set-P dan set-NP adalah set setara. Ia adalah jelas bahawa set-P tergolong dalam set-NP. Namun, masih belum dibuktikan bahawa setiap masalah dalam set NP adalah dalam set P. Jika ini terbukti, ini bermakna setiap masalah yang mudah dikira mempunyai penyelesaian yang mudah untuk diselesaikan, iaitu, kita tidak lagi memerlukan 10^28 tahun untuk menyelesaikan Masalah 2.

Masalah NP dan kehidupan sebenar

Bukan hanya kesukaran matematik masalah P-NP yang menjadikannya salah satu daripada tujuh masalah matematik teratas sepanjang masa. Sebab ia sangat penting untuk dibuktikan ialah ia berkait rapat dengan menyelesaikan masalah dunia sebenar. Masalah dunia sebenar dalam industri yang pelbagai seperti penjadualan kapal terbang, reka bentuk semikonduktor, penempatan mesin gerudi, analisis data genomik, penempatan teleskop astronomi dan kristalografi sinar-X ialah masalah keras NP yang mengambil masa yang lama untuk diselesaikan. Walau bagaimanapun, kami masih belum menemui algoritma untuk membuat keputusan optimum dengan cepat, dan kami tidak tahu sama ada algoritma sedemikian wujud. Jadi, jika tiada algoritma masa polinomial, bagaimanakah kita pada masa ini membuat keputusan tentang masalah dunia sebenar?
Sarjana dalam pelbagai bidang seperti matematik, sains komputer, kejuruteraan industri, dsb. sedang menyelidik dan membangunkan pelbagai penyelesaian anggaran yang menghampiri penyelesaian optimum untuk menyelesaikan masalah dunia sebenar. Pertimbangkan masalah pencuri sekali lagi: jika mencari kombinasi permata yang optimum akan mengambil masa yang lama, alternatifnya ialah mencari jalan untuk membuat keputusan dengan cepat dan cekap dengan keuntungan yang agak kecil. Satu pilihan mungkin adalah untuk mengira nilai setiap berat setiap batu permata dan mengisi beg anda dengan permata dengan nilai tertinggi setiap berat terlebih dahulu. Ini ialah penyelesaian anggaran yang dipanggil heuristik tamak, yang telah digunakan secara praktikal apabila keputusan perlu dibuat dengan cepat. Walaupun anggaran ini tidak optimum, ia sangat membantu dalam membuat keputusan dalam masalah dunia sebenar dengan kekangan masa. Tambahan pula, beberapa penyelesaian anggaran menjadi lebih canggih, dengan beberapa anggaran dapat menganggarkan nilai optimum untuk masalah tertentu dalam ralat 0.5%.

Industri keselamatan dan masalah NP

Berbeza dengan industri di atas, terdapat satu industri yang tidak mahu algoritma mudah ditemui untuk menyelesaikan masalah NP. Ini adalah industri keselamatan. Skim keselamatan semasa disusun dengan cara yang menggunakan masalah NP secara terbalik. Jika anda mengetahui kata laluan, mudah untuk mengesahkan bahawa kata laluan itu betul, tetapi tidak mudah untuk mencarinya kerana tiada algoritma masa polinomial untuk mencarinya. Mungkin seluruh industri keselamatan berharap bahawa masalah P-NP akan kekal sebagai teka-teki abadi.
Walau bagaimanapun, membuktikan P=NP tidak bermakna semua masalah NP mudah diselesaikan. Walau bagaimanapun, adalah jelas bahawa kewujudan algoritma masa polinomial akan mendorong ramai penyelidik untuk mengkaji algoritma masa polinomial untuk masalah NP keras. Ini akan memberi kesan yang ketara ke atas peningkatan kecekapan dan pengoptimuman masalah dunia sebenar. Sebaliknya, jika ternyata P≠NP, bermakna tiada kaedah sedemikian, yang bermaksud bahawa banyak masalah NP akan kekal sukar diatasi di dunia nyata. Sama ada cara, ia akan menjadi menarik untuk melihat apakah keputusan teka-teki ini.