Masalah terbesar dalam sains komputer: P lawan NP

Terdapat tujuh masalah matematik yang dianggap begitu sukar dan menarik sehingga Clay Mathematics Institute menamakannya Masalah Hadiah Milenium. Sesiapa yang menyelesaikan mana-mana satu daripadanya akan menerima ganjaran sebanyak satu juta dolar. Salah satu masalah itu juga berkaitan dengan sains komputer dan dikenali sebagai masalah P lawan NP. Mari kita lihat tentang apakah sebenarnya masalah ini.

Baiklah. Kita tidak perlu berpura-pura bahawa masalah ini mudah diterangkan. Bagaimanapun, ini ialah Masalah Hadiah Milenium. Jadi, sediakan secawan teh hijau yang enak 🍵 dan mari kita mulakan. Mula-mula, kita akan melihat empat masalah yang berlainan daripada dunia sains komputer dan algoritma. Kita akan menganalisis masalah itu dan melihat hubungannya dengan huruf P dan NP.

Masalah 1: Mencari nombor terkecil

P lawan NP berkaitan dengan algoritma dan kerumitannya. Bayangkan saya menaburkan seratus helai kertas di hadapan anda. Pada setiap helai tertulis satu nombor, dan saya meminta anda mencari kertas yang mengandungi nombor terkecil. Berapa lamakah masa yang anda perlukan?

Setengah minit? Dua minit?

Unit masa seperti ini tidak begitu penting dalam sains komputer teori. Yang penting ialah bilangan operasi. Jadi, kita boleh bertanya dengan cara yang sedikit berbeza: berapa helai kertas yang perlu saya periksa untuk memastikan bahawa saya telah menemui nombor terkecil? Jawapannya, saya perlu memeriksa semua kertas — kerana nombor terkecil mungkin berada pada kertas yang terakhir. Jika saya memberikan seratus helai kertas, anda perlu memeriksa seratus helai kertas. Jika saya memberikan seribu helai, anda perlu memeriksa seribu helai. Secara umum, jika saya memberikan n helai kertas, anda perlu memeriksa n helai kertas.

Inilah yang dipanggil kerumitan algoritma. Jika saya memberikan n helai kertas dan anda perlu melakukan n operasi untuk mencari nombor terkecil, maksudnya algoritma untuk mencari nombor terkecil ini mempunyai kerumitan n. Kerumitan ini juga dipanggil kerumitan linear kerana kerumitan itu diperihalkan oleh fungsi linear.

Baiklah, anda telah memeriksa seratus helai kertas dan memberitahu bahawa nombor terkecil ialah 17. Bagaimanakah saya boleh menyemak bahawa anda bercakap benar? Tiada cara lain selain memeriksa semua kertas sekali lagi dan memastikan tiada kertas yang mengandungi nombor yang lebih kecil. Jadi, anda perlu melihat n helai kertas untuk mencari nombor terkecil, dan jika saya ingin menyemaknya, saya perlu melakukan perkara yang sama. Kerumitan pengesahan hasilnya juga n, iaitu kerumitan linear.

Adakah wujud algoritma yang hasilnya lebih mudah disemak daripada dicari?

Masalah 2: Hasil darab pasangan

Bayangkan saya menaburkan dua longgok kertas yang sama besar di hadapan anda. Setiap kertas sekali lagi mengandungi satu nombor. Sekarang saya meminta anda mencari satu nombor daripada longgok A dan satu nombor daripada longgok B supaya hasil darabnya ialah 918. Sebagai contoh, katakan longgok nombor itu seperti berikut:

$$\begin{array}{rcl}A& =& \{49,11,32,54,15\}\\ B& =& \{17,64,74,61,21\}\end{array}$$

Bagaimanakah kita boleh mencari pasangan nombor yang hasil darabnya 918? Kita boleh mencuba semua kemungkinan. Berapakah bilangannya? Agak banyak, iaitu 25. Mula-mula, kita darab nombor pertama daripada longgok A, iaitu 49, dengan setiap nombor daripada longgok B:

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Tiada pasangan yang memberikan 918. Jadi, kita cuba perkara yang sama dengan nombor lain daripada longgok A: lima pasangan lagi bagi nombor 11, lima pasangan lagi bagi nombor 32, lima pasangan lagi bagi 54 dan lima pasangan terakhir bagi 15. Secara keseluruhan, kita boleh mencuba 25 pasangan nombor. Akhirnya, kita dapati bahawa 54 · 17 = 918.

Berapakah kerumitan algoritma ini? Kita ingin tahu berapa pasangan nombor yang perlu didarab. Kedua-dua longgok mengandungi lima helai kertas, dan kita perlu mencuba setiap satu daripada lima nombor dalam longgok pertama dengan setiap satu daripada lima nombor dalam longgok kedua. Secara keseluruhan, kita mencuba 5 · 5 = 25 gabungan. Jika saya memberikan dua longgok yang masing-masing mengandungi 10 helai kertas, anda perlu mencuba 10 · 10 = 100 gabungan. Secara umum, jika saya memberikan dua longgok yang masing-masing mengandungi n helai kertas, anda perlu mencuba n · n = n² gabungan.

Kita katakan bahawa algoritma ini mempunyai kerumitan n², iaitu kerumitan kuadratik, kerana kerumitan itu diperihalkan oleh fungsi kuadratik.

Tetapi berapa sukarkah menyemak hasilnya? Jika anda memberitahu saya bahawa hasil darab 54 dan 17 ialah 918, saya tidak perlu memeriksa semua pasangan nombor daripada kedua-dua longgok seperti yang anda lakukan. Saya hanya perlu mendarab satu pasangan ini, 54 · 17, dan saya akan tahu sama ada anda betul atau tidak. Jadi, untuk menyelesaikan masalah ini, kita perlu menghitung sehingga n² hasil darab, tetapi untuk mengesahkannya, satu hasil darab sudah memadai. Pengesahan mempunyai kerumitan malar 1.

Inilah perbezaan besar berbanding masalah sebelumnya, yang memerlukan bilangan langkah yang sama untuk pengiraan dan untuk pengesahan.

Masalah ini juga jauh lebih rumit daripada masalah sebelumnya. Jika saya menaburkan sepuluh ribu helai kertas di hadapan anda dan meminta anda mencari nombor terkecil, mungkin anda dapat menemuinya dalam sehari. Tetapi jika saya menaburkan dua longgok yang masing-masing mengandungi sepuluh ribu helai kertas dan meminta anda mencari hasil darab itu, anda perlu memeriksa sepuluh ribu darab sepuluh ribu hasil darab, iaitu seratus juta pengiraan. Walaupun anda mencuba satu hasil darab sesaat, anda memerlukan kira-kira tiga tahun.

Masalah 3: Hasil tambah subset

Mari kita lihat masalah ketiga. Kali ini saya menaburkan dua belas helai kertas bernombor di hadapan anda, dan saya meminta anda mencari sebarang bilangan kertas yang hasil tambahnya sifar. Sebagai contoh:

$$A=\{24,-69,1,-15,-76,-60,16,-83,48,-22,54,-47\}$$

Pilih sebarang kumpulan nombor daripada nombor ini yang hasil tambahnya 0. Misalnya, nombor

$$24+48-69+1$$

memberikan hasil tambah 4, jadi kumpulan ini bukan jawapan yang betul. Jawapan yang betul ialah kumpulan nombor… dan anda tahu? Cuba cari sendiri sebagai kerja rumah 😉. Terdapat hanya satu kumpulan nombor yang hasil tambahnya 0. Sekurang-kurangnya anda akan merasai betapa sukarnya masalah ini.

Sekarang kita perlu mengetahui kerumitan masalah ini. Pengiraannya tidak begitu remeh dan lebih sesuai untuk peminat yang benar-benar berminat. Jika anda ingin tahu bagaimana kerumitan masalah ini dihitung, teruskan membaca. Jika tidak, anda boleh melangkau ke bahagian seterusnya. ⏩

Bagaimanakah kita boleh mencari kumpulan nombor yang hasil tambahnya 0? Kita perlu mencuba semua gabungan nombor yang mungkin. Kita perlu mencuba semua pasangan nombor, semua kumpulan tiga, empat, lima nombor dan seterusnya, dan bagi setiap kumpulan kita perlu menyemak sama ada hasil tambahnya sifar. Berapakah bilangan gabungan seperti ini?

Mari kita lihat dengan set nombor yang lebih kecil. Berapakah bilangan kumpulan nombor yang berlainan, atau subset, yang boleh dibentuk daripada tiga nombor B = {5, 7, 9}? Terdapat lapan kesemuanya:

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5,9\}\\ B_6& =& \{5,7\}\\ B_7& =& \{7,9\}\\ B_8& =& \{5,7,9\}\end{array}$$

Perhatikan bahawa kita juga mengira subset kosong B₁. Subset ini tidak begitu berguna sekarang, tetapi kita masukkan supaya senarainya lengkap. Untuk memudahkan pengiraan, kita padankan setiap subset dengan satu vektor binari. Vektor binari hanyalah jujukan sifar dan satu, misalnya 00101010. Kita akan menggunakan vektor binari dengan panjang tiga. Vektor dipadankan seperti berikut: 101 dipadankan dengan subset yang mengandungi “nombor pertama dan ketiga daripada set asal, tetapi bukan nombor kedua”, iaitu set {5, 9}. Vektor 110 dipadankan dengan subset yang mengandungi “nombor pertama dan kedua daripada set asal, tetapi bukan nombor ketiga”, iaitu set {5, 7}, dan seterusnya.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5,9\}& \to & 101\\ B_6=\{5,7\}& \to & 110\\ B_7=\{7,9\}& \to & 011\\ B_8=\{5,7,9\}& \to & 111\end{array}$$

Kita lihat bahawa setiap subset mempunyai tepat satu vektor binari dengan panjang tiga, dan setiap vektor binari dengan panjang tiga sepadan dengan tepat satu subset. Jadi, jika kita mengira berapa banyak vektor binari yang berlainan dengan panjang n, kita akan mendapat bilangan gabungan yang boleh dibentuk daripada n nombor yang berlainan. Mari kita hitung.

Terdapat dua vektor binari dengan panjang satu: 0 dan 1.

Vektor binari dengan panjang dua diperoleh dengan mengambil semua vektor binari dengan panjang satu dan menambah 0 pada hujung setiap vektor: kita peroleh vektor 00 dan 10. Sekali lagi, kita ambil semua vektor dengan panjang 1 dan menambah 1 pada hujungnya: 01 dan 11. Dengan ini, kita memperoleh semua vektor dengan panjang 2: 00, 01, 10 dan 11.

Vektor binari dengan panjang tiga diperoleh dengan mengambil semua vektor binari dengan panjang dua dan menambah sifar pada hujungnya: 000, 010, 100 dan 110, serta satu: 001, 011, 101 dan 111.

Begitulah seterusnya bagi setiap panjang. Kita lihat bahawa apabila panjang vektor binari bertambah satu, bilangan vektor binari yang berlainan menjadi dua kali ganda. Bagi vektor dengan panjang empat, kita memperoleh 2 · 2 · 2 · 2, iaitu 16, gabungan yang berlainan.

Secara umum, kita boleh menyimpulkan bahawa jika set M mengandungi n unsur, bilangan semua subset bagi set M ini sama dengan bilangan semua vektor binari yang berlainan dengan panjang n, iaitu

$$\underset{n\text{ kali}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

2ⁿ atau n² — bukankah sama sahaja? 🤷‍♂

Jadi, terdapat 2ⁿ subset yang berlainan yang boleh dibentuk daripada set yang mengandungi n nombor. Dalam kes kita, terdapat n = 12 nombor, jadi kita perlu memeriksa 2¹² gabungan yang berlainan, iaitu 4096 gabungan. Kita katakan bahawa masalah ini mempunyai kerumitan 2ⁿ, iaitu kerumitan eksponen, kerana kerumitan itu diperihalkan oleh fungsi eksponen.

Perhatikan bahawa masalah sebelumnya mempunyai kerumitan n², manakala masalah ini mempunyai kerumitan 2ⁿ. Kelihatan sangat serupa, bukan? Namun, terdapat perbezaan besar antara indeks yang malar dengan indeks yang berupa pemboleh ubah n. Perhatikan bahawa apabila n = 4, kita peroleh

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Baiklah, setakat ini hasilnya sama. Bagaimana pula jika n = 10?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Wah, fungsi eksponen melonjak dan tiba-tiba menjadi kira-kira sepuluh kali ganda nilai fungsi kuadratik. Apakah yang kita peroleh bagi n = 20?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1048576\end{array}$$

Bagi n = 20, nilai kerumitan eksponen kira-kira 2600 kali ganda nilai kerumitan kuadratik. Jadi, kita lihat bahawa fungsi eksponen bertambah jauh lebih pantas daripada fungsi kuadratik. Ingatlah perkara ini apabila kita dilanda pandemik lagi yang merebak dalam populasi secara eksponen.

Jadi, jika saya memberikan dua puluh helai kertas, anda perlu memeriksa 1 048 576 gabungan. Jumlah itu agak banyak.

Bagaimanakah kita mengesahkan bahawa hasilnya betul?

Berapa lamakah masa yang saya perlukan untuk mengesahkan bahawa kumpulan nombor yang diperoleh memang memberikan hasil tambah 0? Hal ini agak cepat: saya hanya perlu menambah nombor dalam kumpulan ini. Jika hasil tambahnya 0, anda telah menemui kumpulan kertas yang betul. Jika hasil tambahnya nombor lain, kumpulan kertas itu salah.

Sekali lagi, kita lihat bahawa menyemak hasil jauh lebih mudah daripada mencarinya.

Masalah 4: Masalah jurujual kembara

Masalah jurujual kembara ialah salah satu masalah algoritma yang paling terkenal. Secara ringkas, terdapat seorang jurujual kembara yang menjual barang. Jurujual ini perlu banyak mengembara untuk mencari rezeki. Oleh itu, dia memutuskan untuk melawat ibu negeri bagi setiap negeri di Malaysia serta ibu negara, Kuala Lumpur. Oleh sebab dia tidak mahu membazir, dia memutuskan untuk mencari laluan terpendek yang melalui semua bandar itu. Tugas kita ialah mencari laluan terpendek tersebut.

Bagaimanakah kita boleh mencari laluan terpendek ini? Kita cuba semua kemungkinan.

Kita boleh memudahkan masalah ini. Andaikan antara setiap dua bandar terdapat tepat satu laluan terpendek. Bagaimanakah kita boleh mencari laluan terpendek yang melalui semua bandar? Malaysia mempunyai 13 negeri, jadi terdapat 13 ibu negeri dan Kuala Lumpur, iaitu 14 bandar. Jadi, terdapat 14 pilihan tempat untuk bermula. Katakan kita bermula di Ipoh!!! Ke manakah kita boleh pergi dari Ipoh? Secara teori, kita boleh pergi ke mana-mana bandar lain. Jadi, kita boleh memilih daripada 13 bandar yang tinggal.

Sekarang pun kita boleh mengira bahawa terdapat 14 · 13 cara untuk melawat dua bandar pertama — terdapat 14 pilihan tempat untuk bermula, kemudian kita boleh memilih daripada 13 bandar yang tinggal.

Apabila sampai di bandar kedua, kita perlu meneruskan perjalanan. Kita sudah melawat dua bandar, jadi kita boleh pergi ke salah satu daripada 12 bandar yang tinggal. Secara keseluruhan, terdapat 14 · 13 · 12 cara untuk melawat tiga bandar pertama.

Selepas melawat bandar ketiga, kita perlu memilih satu daripada 11 bandar yang tinggal, kemudian satu daripada 10 bandar yang tinggal, dan seterusnya.

Apabila kita telah melawat semua bandar, kita dapati bahawa terdapat

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

pilihan. Hal ini mungkin mengingatkan anda kepada faktorial, yang ditandakan dengan tanda seru. Jadi, kita boleh mengatakan bahawa hasil darab ini sama dengan 14!:

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

Maka, terdapat 14! laluan yang melalui semua bandar itu. Adakah jumlah ini besar? Ya, agak besar, kerana

$$14!=87178291200.$$

Secara umum, jika kita mencari laluan terpendek antara n bandar, kita perlu mencuba n! laluan yang berlainan. Jadi, kerumitan penyelesaian ini ialah n!.

Bagaimanakah kita mengesahkan bahawa kita telah menemui hasil yang betul? Jika anda memberitahu saya bahawa laluan terpendek bermula dari Kuching ke Ipoh, kemudian ke Johor Bahru dan seterusnya, bagaimanakah saya boleh mengesahkan bahawa anda bercakap benar? Hal ini agak sukar 🤷‍♂. Apabila saya melihat laluan itu, saya tidak dapat menyemak dengan mudah sama ada laluan itu memang yang terpendek. Sebenarnya saya perlu mengulang seluruh pengiraan. Jadi, pengesahan hasilnya juga mempunyai kerumitan n!.

Kelas P dan NP

Kita telah melihat empat masalah dan algoritma yang menyelesaikannya, serta menganalisis betapa rumitnya mencari penyelesaian dan betapa rumitnya menyemak penyelesaian itu. Kita boleh meringkaskannya dalam jadual ini:

Sekarang kita bahagikan masalah kita kepada dua kumpulan. Kumpulan pertama terdiri daripada masalah yang mudah diselesaikan. Masalah ini boleh diselesaikan dengan kerumitan n, n², n³, n⁴ dan seterusnya. Oleh sebab ungkapan seperti n² dipanggil polinomial, kelas masalah ini ditandakan dengan huruf P. Jadi, kita katakan bahawa kelas P mengandungi masalah yang boleh diselesaikan dalam masa polinomial (iaitu mempunyai kerumitan seperti n² atau n⁷). Secara umum, masalah ini boleh diselesaikan dengan agak mudah.

Masalah 1, mencari nombor terkecil, tergolong dalam kelas P kerana kerumitan penyelesaiannya ialah n. Masalah 2, hasil darab pasangan, juga tergolong dalam kelas ini kerana kerumitan penyelesaiannya ialah n². Kedua-duanya ialah polinomial.

Kelas kedua ialah kelas NP. Kelas ini mengandungi masalah yang boleh disahkan dalam masa polinomial. Jadi, semua masalah kecuali yang terakhir tergolong dalam kelas NP. Kita tidak dapat mengesahkan masalah jurujual kembara dalam masa polinomial. Tiga masalah sebelumnya boleh disahkan dalam masa polinomial.

Kita tidak dapat menyelesaikan atau mengesahkan masalah jurujual kembara dalam masa polinomial. Bagi masalah jurujual kembara, kita memerlukan satu lagi kelas yang mengandungi masalah yang lebih sukar. Kelas ini wujud, tetapi buat masa ini tidak penting bagi kita.

Jelas bahawa kelas P ialah subset bagi kelas NP. Maksudnya, setiap masalah dalam kelas P juga berada dalam kelas NP. Hal ini munasabah — jika kita dapat menyelesaikan sesuatu masalah dalam masa polinomial, kita juga dapat mengesahkan hasilnya dalam masa polinomial.

Masalah P lawan NP

Adakah sebaliknya juga benar? Adakah setiap masalah dalam kelas NP juga berada dalam kelas P? Dengan kata lain, jika terdapat cara untuk mengesahkan hasil sesuatu masalah dalam masa polinomial, adakah juga terdapat algoritma yang menyelesaikan masalah itu dalam masa polinomial?

Sebagai contoh, kita tahu bahawa kita dapat mengesahkan hasil masalah 3, hasil tambah subset, dalam masa polinomial. Tetapi untuk menyelesaikannya, kita menggunakan algoritma yang tidak polinomial. Algoritma itu mempunyai kerumitan eksponen 2ⁿ. Namun, adakah kita tahu dengan pasti bahawa tiada algoritma dengan kerumitan polinomial bagi masalah ini?

Kita tidak tahu!

Mungkin sahaja bagi setiap masalah yang boleh disahkan dalam masa polinomial, terdapat algoritma yang menyelesaikan masalah itu dalam masa polinomial. Kita tidak tahu. Kita tidak dapat membuktikan kewujudan algoritma seperti itu, tetapi kita juga tidak dapat menyangkal kewujudannya.

Jika bagi setiap masalah dalam kelas NP terdapat algoritma yang menyelesaikannya dalam masa polinomial, maksudnya kelas NP sebenarnya sama dengan kelas P. Semua masalah dalam kelas P berada dalam kelas NP, dan semua masalah dalam kelas NP berada dalam kelas P — kedua-dua kelas itu sama, iaitu serupa sepenuhnya.

Jadi, masalah P lawan NP ialah persoalan sama ada kelas P sama dengan kelas NP, atau kedua-duanya ialah dua kelas masalah yang berlainan.

Sama ada P = NP atau P ≠ NP. Tiada siapa yang tahu. Jika anda menemui jawapannya, anda akan menerima ganjaran satu juta dolar, kemasyhuran yang kekal dan mungkin juga Anugerah Turing, iaitu sejenis Hadiah Nobel bagi sains komputer.

Apakah yang akan berlaku jika P = NP?

Apakah yang akan berlaku jika P = NP? Sebenarnya tidak mudah untuk mengatakannya. Kita akan tahu bahawa bagi semua masalah dalam kelas NP, terdapat algoritma yang menyelesaikannya dalam masa polinomial. Misalnya, bagi masalah 3, hasil tambah subset, terdapat algoritma yang menyelesaikannya dalam masa polinomial. Namun, ada tiga perkara yang perlu diberi perhatian:

• Walaupun kita tahu bahawa algoritma seperti itu wujud, tidak semestinya kita dapat menemuinya. Kita hanya tahu bahawa ya, terdapat algoritma yang menyelesaikan masalah itu dalam masa polinomial, tetapi mungkin kita tidak dapat membinanya selama seratus tahun lagi. Hal ini serupa dengan teori kerelatifan am yang meramalkan kewujudan lohong hitam, tetapi kita masih memerlukan beberapa dekad sebelum dapat merakam “gambar” pertama lohong hitam.
• Malangnya, kewujudan algoritma yang berfungsi dalam masa polinomial tidak bermaksud algoritma itu pantas. Kita mungkin menemui algoritma dengan kerumitan n¹⁰⁰. Ungkapan n¹⁰⁰ juga ialah polinomial. Jika kita membandingkan kerumitan 2ⁿ dengan n¹⁰⁰, kita dapati bahawa selagi n agak kecil, algoritma dengan kerumitan 2ⁿ masih memerlukan operasi yang lebih sedikit. Misalnya, bagi n = 20, 2²⁰ = 1 048 576, manakala ungkapan 20¹⁰⁰ memberikan nombor yang mempunyai kira-kira 130 digit, iaitu nombor yang 120 tertib magnitud lebih besar daripada 1 048 576. Jadi, dalam realiti, algoritma polinomial kita lebih perlahan daripada algoritma eksponen. Sekurang-kurangnya selagi n agak kecil.
• Jika kita benar-benar dapat menemui algoritma pantas yang berfungsi dalam masa polinomial, kita dapat menyelesaikan banyak masalah dengan lebih cepat dan lebih tepat. Hal ini tentu sahaja berita baik, tetapi ada juga keburukannya. Terdapat satu bidang yang bergantung pada hakikat bahawa sesetengah masalah sukar diselesaikan, iaitu kriptografi — penyulitan. Mungkin sifer yang digunakan sekarang akan menjadi jauh lebih mudah dipecahkan.

Selingan: oleh sebab anda telah membaca sehingga ke sini, sebagai ganjaran saya akan mendedahkan bahawa penyelesaian masalah 3 ialah 24 + 1 − 60 + 16 − 83 + 48 + 54.

Apakah yang akan berlaku jika P ≠ NP?

Jika kelas masalah P dan NP berlainan, tidak banyak yang akan berlaku kerana keadaan itu lebih kurang sama dengan keadaan sekarang. Pada masa ini, kita tidak mempunyai sebarang algoritma yang menyelesaikan masalah sukar dalam NP dalam masa polinomial. Jika seseorang membuktikan bahawa P ≠ NP, keadaan ini akan kekal selama-lamanya. Bukti bahawa P = NP akan menjadi berita sensasi yang jauh lebih besar.

Rujukan dalam budaya popular

• Dalam satu episod The Simpsons, Homer masuk ke dalam sejenis realiti alternatif, dan di situ dia melihat bahawa P = NP. Anda boleh menontonnya di youtube.com.
• Dalam Futurama pula, kita boleh melihat dua fail dalam sebuah gudang, satu berlabel P dan satu lagi berlabel NP. Anda boleh menontonnya di youtube.com.
• Episod kedua musim kedua siri Elementary yang bertajuk “Solve for X” mengisahkan pembunuhan seorang ahli matematik yang mungkin telah menyelesaikan masalah P lawan NP.