Masalah terbesar dalam ilmu komputer: P versus NP

Ada tujuh masalah matematika yang dianggap begitu sulit dan menarik sehingga Clay Mathematics Institute menyebutnya masalah milenium. Siapa pun yang memecahkan salah satunya akan mendapat hadiah satu juta dolar. Salah satu masalah itu juga menyangkut ilmu komputer dan disebut masalah P versus NP. Mari kita lihat sebenarnya tentang apa masalah ini.

Begini. Jangan membohongi diri sendiri: menjelaskannya tidak akan mudah. Bagaimanapun, ini masalah milenium. Jadi, seduhlah dulu teh hijau yang enak 🍵, lalu kita mulai. Pertama, kita akan melihat empat masalah yang berbeda dari dunia ilmu komputer dan algoritma. Masalah-masalah itu akan kita analisis, lalu kita lihat hubungannya dengan huruf P dan NP.

Masalah 1: Mencari bilangan terkecil

P vs. NP berkaitan dengan algoritma dan kompleksitasnya. Bayangkan saya menebarkan seratus lembar kertas di depanmu. Pada setiap kertas tertulis satu bilangan, dan saya memintamu menemukan kertas yang bertuliskan bilangan terkecil. Berapa lama waktu yang kamu perlukan?

Setengah menit? Dua menit?

Satuan waktu seperti itu tidak terlalu menarik dalam ilmu komputer teoretis. Yang kita perhatikan lebih tepatnya adalah banyaknya operasi. Jadi, pertanyaannya bisa diubah sedikit: berapa lembar kertas yang harus saya periksa agar saya yakin sudah menemukan bilangan terkecil? Jawabannya: saya harus memeriksa semua kertas, karena bilangan terkecil bisa saja ada di kertas terakhir. Jika saya menebarkan seratus kertas di depanmu, kamu harus memeriksa seratus kertas. Jika saya menebarkan seribu, kamu harus memeriksa seribu. Secara umum, jika saya menebarkan n kertas di depanmu, kamu harus memeriksa n kertas.

Inilah yang disebut kompleksitas algoritma. Jika saya menebarkan n kertas di depanmu dan kamu harus melakukan n operasi untuk menemukan bilangan terkecil, algoritma pencarian bilangan terkecil ini mempunyai kompleksitas n. Kompleksitas ini disebut juga kompleksitas linear, karena dinyatakan oleh fungsi linear.

Baik, kamu sudah memeriksa seratus kertas dan mengumumkan bahwa bilangan terkecil adalah 17. Bagaimana saya bisa memeriksa bahwa kamu berkata benar? Tidak ada cara lain selain memeriksa lagi semua kertas dan memastikan bahwa tidak ada bilangan yang lebih kecil. Jadi, kamu harus melihat n kertas untuk menemukan bilangan terkecil, dan jika ingin memeriksanya, saya harus melakukan hal yang sama. Kompleksitas verifikasi hasilnya juga n, yaitu kompleksitas linear.

Adakah algoritma yang hasilnya lebih mudah diperiksa daripada ditemukan?

Masalah 2: Hasil kali pasangan

Bayangkan saya menebarkan dua tumpukan kertas yang sama besar di depanmu. Pada setiap kertas tertulis lagi satu bilangan. Sekarang saya memintamu menemukan sebuah bilangan dari tumpukan A dan sebuah bilangan dari tumpukan B yang hasil kalinya 918. Sebagai contoh, misalkan tumpukan bilangannya seperti ini:

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

Bagaimana kita dapat menemukan pasangan bilangan yang hasil kalinya sama dengan 918? Kita bisa saja mencoba semua kemungkinan. Ada berapa kemungkinan? Cukup banyak, yaitu 25. Kita mulai dengan mengalikan bilangan pertama dari tumpukan A, yaitu 49, dengan setiap bilangan dari tumpukan 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}$$

Tidak ada pasangan yang menghasilkan 918. Jadi, kita lakukan hal yang sama dengan bilangan lain dari tumpukan A: lima pasangan lagi untuk bilangan 11, lima pasangan lagi untuk 32, lima pasangan lagi untuk 54, dan lima pasangan terakhir untuk 15. Seluruhnya kita bisa mencoba 25 pasangan bilangan. Akhirnya kita menemukan bahwa 54 · 17 = 918.

Berapa kompleksitas algoritma ini? Yang kita perhatikan adalah berapa pasangan bilangan yang harus kita kalikan. Kedua tumpukan berisi lima kertas, dan kita harus mencoba setiap bilangan dari tumpukan pertama dengan setiap bilangan dari tumpukan kedua. Seluruhnya kita mencoba 5 · 5 = 25 kombinasi. Jika saya menebarkan dua tumpukan berisi 10 kertas, kamu harus mencoba 10 · 10 = 100 kombinasi. Secara umum, jika saya menebarkan dua tumpukan berisi n kertas, kamu harus mencoba n · n = n² kombinasi.

Kita katakan bahwa algoritma ini mempunyai kompleksitas n², yaitu kompleksitas kuadratik, karena dinyatakan oleh fungsi kuadrat.

Lalu, seberapa sulit memeriksa hasilnya? Jika kamu menjawab bahwa 54 dan 17 adalah bilangan yang hasil kalinya 918, saya tidak perlu lagi memeriksa semua pasangan bilangan dari kedua tumpukan seperti yang harus kamu lakukan. Cukup saya kalikan satu pasangan ini, 54 · 17, dan saya akan tahu apakah kamu benar atau tidak. Jadi, untuk menyelesaikan masalah ini perlu dihitung sampai n² hasil kali, tetapi untuk memverifikasinya cukup dihitung satu hasil kali. Verifikasi mempunyai kompleksitas konstan 1.

Dengan begitu, soal ini sangat berbeda dari soal sebelumnya, yang membutuhkan langkah yang sama banyak untuk perhitungan dan untuk verifikasi.

Soal ini juga jauh lebih rumit daripada soal sebelumnya. Jika saya menebarkan sepuluh ribu kertas di depanmu dan memintamu mencari bilangan terkecil, mungkin kamu bisa menemukannya dalam sehari. Namun, jika saya menebarkan dua tumpukan berisi sepuluh ribu kertas dan memintamu mencari hasil kali tadi, kamu harus memeriksa sepuluh ribu kali sepuluh ribu hasil kali, yaitu seratus juta perhitungan. Bahkan jika kamu mencoba satu hasil kali per detik, kamu akan membutuhkan sekitar tiga tahun.

Masalah 3: Jumlah subhimpunan

Mari kita lihat masalah ketiga. Kali ini saya menebarkan dua belas kertas berisi bilangan di depanmu, dan saya memintamu memilih sejumlah kertas, berapa pun banyaknya, yang jumlah bilangannya nol. Sebagai contoh:

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

Pilihlah dari bilangan-bilangan ini sembarang kelompok bilangan yang jumlahnya 0. Misalnya, bilangan

$$24+48-69+1$$

jumlahnya 4, sehingga bukan jawaban yang benar. Jawaban yang benar adalah kelompok bilangan… eh, tahu tidak? Coba cari sendiri sebagai pekerjaan rumah 😉. Hanya ada satu kelompok bilangan yang jumlahnya 0. Setidaknya kamu bisa merasakan sendiri betapa sulitnya masalah ini.

Sekarang kita perlu mengetahui kompleksitas masalah ini. Perhitungannya tidak lagi sepele dan lebih cocok untuk penggemar yang serius. Jika kamu ingin tahu bagaimana kompleksitas masalah ini dihitung, lanjutkan membaca. Jika tidak, kamu boleh langsung lompat ke bagian berikutnya. ⏩

Bagaimana kita dapat menemukan kelompok bilangan yang jumlahnya 0? Kita harus mencoba semua kombinasi bilangan yang mungkin. Kita harus mencoba semua pasangan bilangan, semua kelompok tiga bilangan, empat bilangan, lima bilangan, dan seterusnya, lalu untuk setiap kelompok kita periksa apakah jumlahnya nol. Ada berapa banyak kombinasi seperti itu?

Mari kita lihat pada himpunan bilangan yang lebih kecil. Berapa banyak kelompok bilangan yang berbeda, atau himpunan bagian, yang dapat dibentuk dari tiga bilangan B = {5, 7, 9}? Seluruhnya ada delapan:

$$\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 bahwa kita juga menghitung himpunan bagian kosong B₁. Saat ini himpunan itu tidak terlalu berguna, tetapi demi kerapian kita tetap mencantumkannya. Agar perhitungannya lebih sederhana, setiap himpunan bagian kita pasangkan dengan sebuah vektor biner. Vektor biner hanyalah deretan angka nol dan satu, misalnya 00101010. Kita akan bekerja dengan vektor biner yang panjangnya tiga. Vektor dipasangkan sebagai berikut: 101 dipasangkan dengan himpunan bagian yang memuat “bilangan pertama dan ketiga dari himpunan semula, tetapi bukan bilangan kedua”, yaitu himpunan {5, 9}. Vektor 110 dipasangkan dengan himpunan bagian yang memuat “bilangan pertama dan kedua dari himpunan semula, tetapi bukan bilangan ketiga”, yaitu himpunan {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}$$

Terlihat bahwa setiap himpunan bagian mempunyai tepat satu vektor biner yang panjangnya tiga, dan setiap vektor biner yang panjangnya tiga sesuai dengan tepat satu himpunan bagian. Jadi, jika kita menghitung banyaknya vektor biner berbeda yang panjangnya n, kita memperoleh banyaknya kombinasi berbeda yang dapat disusun jika input berupa n bilangan yang berbeda. Mari kita hitung.

Ada dua vektor biner yang panjangnya satu: 0 dan 1.

Vektor biner yang panjangnya dua diperoleh dengan mengambil semua vektor biner yang panjangnya satu, lalu menambahkan 0 di akhir setiap vektor: diperoleh vektor 00 dan 10. Kemudian kita ambil lagi semua vektor yang panjangnya 1 dan menambahkan 1 di akhirnya: 01 dan 11. Dengan begitu kita memperoleh semua vektor yang panjangnya 2: 00, 01, 10, dan 11.

Vektor biner yang panjangnya tiga diperoleh dengan mengambil semua vektor biner yang panjangnya dua, lalu menambahkan nol di akhirnya: 000, 010, 100, dan 110, serta menambahkan satu: 001, 011, 101, dan 111.

Begitu seterusnya untuk setiap panjang berikutnya. Terlihat bahwa jika panjang vektor biner bertambah satu, banyaknya vektor biner yang berbeda menjadi dua kali lipat. Jadi, untuk vektor yang panjangnya empat kita akan memperoleh seluruhnya 2 · 2 · 2 · 2, yaitu 16, kombinasi yang berbeda.

Secara umum dapat disimpulkan: jika himpunan M memuat n anggota, banyaknya semua himpunan bagian dari M sama dengan banyaknya semua vektor biner berbeda yang panjangnya n, yaitu

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

2ⁿ atau n², bukankah sama saja? Tentu tidak 🤷‍♂

Jadi, ada 2ⁿ himpunan bagian berbeda yang dapat dibentuk dari himpunan berisi n bilangan. Dalam contoh kita ada n = 12 bilangan, sehingga kita harus memeriksa 2¹² kombinasi yang berbeda, yaitu 4096 kombinasi. Kita katakan bahwa masalah ini mempunyai kompleksitas 2ⁿ, yaitu kompleksitas eksponensial, karena dinyatakan oleh fungsi eksponensial.

Perhatikan bahwa masalah sebelumnya mempunyai kompleksitas n², sedangkan masalah ini mempunyai kompleksitas 2ⁿ. Kelihatannya sangat mirip, bukan? Namun, ada perbedaan besar antara pangkat yang konstan dan pangkat berupa variabel n. Perhatikan bahwa untuk n = 4 kita peroleh

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

Baik, sejauh ini hasilnya sama. Bagaimana jika n = 10?

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

Wah, fungsi eksponensial melonjak dan tiba-tiba sekitar sepuluh kali lebih besar daripada fungsi kuadrat. Apa yang kita peroleh untuk n = 20?

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

Untuk n = 20, kompleksitas eksponensial nilainya sekitar 2.600 kali lebih besar daripada kompleksitas kuadratik. Jadi, fungsi eksponensial tumbuh jauh lebih cepat daripada fungsi kuadrat. Ingatlah hal ini saat kita kembali dilanda pandemi yang menyebar di masyarakat dengan laju eksponensial.

Jadi, jika saya menebarkan dua puluh kertas di depanmu, kamu harus memeriksa 1.048.576 kombinasi. Itu cukup banyak.

Bagaimana memverifikasi kebenaran hasilnya?

Berapa lama waktu yang saya perlukan untuk memverifikasi bahwa kelompok bilangan yang ditemukan memang berjumlah 0? Cukup cepat. Saya cukup menjumlahkan satu kelompok bilangan itu. Jika jumlahnya 0, berarti kamu menemukan kelompok kertas yang benar. Jika jumlahnya lain, berarti kelompok kertas yang kamu temukan salah.

Sekali lagi terlihat bahwa memeriksa hasil jauh lebih mudah daripada menemukannya.

Masalah 4: Masalah pedagang keliling

Masalah pedagang keliling adalah salah satu masalah algoritmik yang paling terkenal. Secara garis besar, ada seorang pedagang keliling yang menjual hujan. Pedagang ini harus sering bepergian agar bisa mencari nafkah. Karena itu, ia memutuskan untuk mengunjungi 14 kota besar di Indonesia. Karena tidak mau boros, ia memutuskan mencari rute terpendek yang melewati semua 14 kota itu. Tugas kita adalah menemukan rute terpendek tersebut.

Bagaimana kita dapat menemukan rute terpendek itu? Kita coba semua kemungkinan.

Kita bisa menyederhanakannya. Bayangkan bahwa di antara setiap dua kota hanya ada satu jalan terpendek. Bagaimana kita dapat menemukan rute terpendek yang melewati semua kota? Ada 14 kota. Jadi, ada 14 pilihan untuk memulai. Misalkan kita memulai dari Medan!!! Dari Medan kita bisa pergi ke mana? Secara teoretis, kita bisa pergi ke kota mana pun yang lain. Jadi, kita bisa memilih dari 13 kota yang tersisa.

Sekarang pun sudah bisa kita hitung bahwa seluruhnya ada 14 · 13 kemungkinan untuk mengunjungi dua kota pertama: ada 14 pilihan untuk memulai, lalu ada 13 kota tersisa yang bisa dipilih.

Setelah sampai di kota kedua, kita harus melanjutkan perjalanan. Kita sudah berada di dua kota, sehingga kita bisa pergi ke salah satu dari 12 kota yang tersisa. Jadi, seluruhnya ada 14 · 13 · 12 kemungkinan untuk mengunjungi tiga kota pertama.

Setelah mengunjungi kota ketiga, kita harus memilih salah satu dari 11 kota yang tersisa, lalu salah satu dari 10 kota yang tersisa, dan seterusnya.

Setelah semua kota dikunjungi, kita mendapati bahwa seluruhnya kita bisa memilih dari

$$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$$

kemungkinan. Hal ini mungkin mengingatkanmu pada faktorial, yang dilambangkan dengan tanda seru. Jadi, kita dapat mengatakan bahwa hasil kali 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$$

Jadi, ada 14! rute yang melewati semua 14 kota tersebut. Apakah itu banyak? Lumayan, karena

$$14!=87178291200.$$

Secara umum, jika kita mencari rute terpendek yang melewati n kota, kita harus mencoba n! rute yang berbeda. Jadi, kompleksitas penyelesaiannya adalah n!.

Bagaimana kita memverifikasi bahwa kita menemukan hasil yang benar? Jika kamu mengatakan bahwa rute terpendek adalah dari Semarang ke Medan, lalu ke Surabaya, dan seterusnya, bagaimana saya bisa memeriksa bahwa kamu berkata benar? Ya, sulit sekali 🤷‍♂. Jika saya melihat rute itu, saya tidak punya cara mudah untuk memeriksa apakah rute itulah yang terpendek. Sebenarnya, saya harus mengulang seluruh perhitungan. Jadi, verifikasi hasilnya juga mempunyai kompleksitas n!.

Kelas P dan NP

Kita sudah melihat empat masalah dan algoritma yang menyelesaikannya, lalu menganalisis seberapa sulit menemukan penyelesaian dan seberapa sulit memeriksa penyelesaian tersebut. Ringkasannya ada pada tabel berikut:

Sekarang masalah-masalah kita bagi menjadi dua kelompok. Kelompok pertama berisi masalah yang mudah diselesaikan, yaitu masalah yang dapat diselesaikan dengan kompleksitas n, n², n³, n⁴, dan seterusnya. Karena bentuk seperti n² disebut polinomial, kelas masalah ini dilambangkan dengan huruf P. Jadi, kelas P berisi masalah yang dapat diselesaikan dalam waktu polinomial (= kompleksitasnya misalnya n² atau n⁷). Secara umum, ini adalah masalah yang dapat diselesaikan dengan cukup mudah.

Kelas P memuat masalah 1, yaitu mencari bilangan terkecil, karena kompleksitas penyelesaiannya n. Kelas ini juga memuat masalah 2, yaitu hasil kali pasangan, karena kompleksitas penyelesaiannya n². Keduanya polinomial.

Kelas kedua adalah kelas NP. Kelas ini berisi masalah yang dapat diverifikasi dalam waktu polinomial. Jadi, kelas NP memuat semua masalah kecuali yang terakhir. Masalah pedagang keliling dalam versi optimasi ini (mencari rute terpendek) tidak dapat kita verifikasi dalam waktu polinomial. Tiga masalah sebelumnya dapat diverifikasi dalam waktu polinomial.

Versi optimasi masalah pedagang keliling sejauh ini tidak dapat kita selesaikan maupun verifikasi dalam waktu polinomial. Untuk versi ini kita membutuhkan kelas lain yang berisi masalah yang lebih sulit lagi. Kelas itu memang ada, tetapi saat ini tidak menarik bagi kita. (Versi keputusannya, yaitu pertanyaan apakah ada rute yang lebih pendek daripada panjang tertentu, justru termasuk kelas NP: panjang rute yang ditunjukkan cukup dijumlahkan.)

Jelas bahwa kelas P adalah himpunan bagian dari kelas NP. Artinya, setiap masalah dalam kelas P juga termasuk kelas NP. Hal ini masuk akal: jika kita mampu menyelesaikan suatu masalah dalam waktu polinomial, kita juga mampu memverifikasi hasilnya dalam waktu polinomial.

Masalah P vs. NP

Apakah sebaliknya juga berlaku? Apakah setiap masalah dari kelas NP juga termasuk kelas P? Dengan kata lain, jika ada cara untuk memverifikasi hasil suatu masalah dalam waktu polinomial, apakah ada juga algoritma yang menyelesaikan masalah tersebut dalam waktu polinomial?

Sebagai contoh, kita tahu bahwa hasil masalah 3, jumlah subhimpunan, dapat diverifikasi dalam waktu polinomial. Namun, untuk menyelesaikannya kita memakai algoritma yang tidak polinomial. Algoritma yang dipakai mempunyai kompleksitas eksponensial 2ⁿ. Apakah kita tahu pasti bahwa untuk masalah ini tidak ada algoritma dengan kompleksitas polinomial?

Tidak tahu!

Bisa saja untuk setiap masalah yang dapat diverifikasi dalam waktu polinomial terdapat algoritma yang menyelesaikannya dalam waktu polinomial. Kita tidak tahu. Kita tidak dapat membuktikan keberadaan algoritma seperti itu, tetapi juga tidak dapat membantahnya.

Seandainya untuk setiap masalah dari kelas NP ada algoritma yang menyelesaikannya dalam waktu polinomial, artinya kelas NP sebenarnya sama dengan kelas P. Semua masalah dari kelas P termasuk kelas NP, dan semua masalah dari kelas NP termasuk kelas P. Kedua kelas akan sama persis.

Jadi, masalah P vs. NP adalah pertanyaan apakah kelas P sama dengan kelas NP, atau keduanya merupakan dua kelas masalah yang berbeda.

Yang berlaku hanya salah satu: P = NP atau P ≠ NP. Tidak ada yang tahu jawabannya. Jika kamu menemukannya, hadiah satu juta dolar, ketenaran abadi, dan kemungkinan besar juga Turing Award sudah menantimu. Turing Award adalah semacam Hadiah Nobel untuk ilmu komputer.

Apa yang terjadi jika P = NP?

Apa yang terjadi seandainya berlaku P = NP? Tidak mudah mengatakannya. Kita akan tahu bahwa untuk semua masalah dari kelas NP ada algoritma yang menyelesaikannya dalam waktu polinomial. Misalnya, untuk masalah 3, jumlah subhimpunan, ada algoritma yang menyelesaikannya dalam waktu polinomial. Hanya saja, ada tiga hal yang perlu diperhatikan:

• Mengetahui bahwa algoritma seperti itu ada tidak berarti kita mampu menemukannya. Kita akan tahu bahwa memang ada algoritma yang menyelesaikan masalah itu dalam waktu polinomial, tetapi mungkin kita baru bisa menyusunnya seratus tahun lagi. Mirip dengan teori relativitas umum yang meramalkan adanya lubang hitam, padahal kita masih membutuhkan beberapa dekade lagi sebelum berhasil membuat “foto” lubang hitam yang pertama.
• Adanya algoritma yang bekerja dalam waktu polinomial sayangnya belum berarti algoritma itu cepat. Bisa saja kita menemukan algoritma dengan kompleksitas n¹⁰⁰. Bentuk n¹⁰⁰ pun merupakan polinomial. Jika kompleksitas 2ⁿ dan n¹⁰⁰ kita bandingkan, ternyata selama n relatif kecil, algoritma dengan kompleksitas 2ⁿ masih membutuhkan lebih sedikit operasi. Misalnya, untuk n = 20 berlaku 2²⁰ = 1.048.576, sedangkan bentuk 20¹⁰⁰ menghasilkan bilangan dengan sekitar 130 angka, yaitu bilangan yang sekitar 120 orde lebih besar daripada 1.048.576. Dalam kenyataannya, algoritma polinomial kita akan lebih lambat daripada algoritma eksponensial, setidaknya selama n relatif kecil.
• Seandainya kita akhirnya berhasil menemukan algoritma cepat yang bekerja dalam waktu polinomial, kita bisa menyelesaikan banyak masalah dengan lebih cepat dan lebih akurat. Tentu saja ini kabar baik, tetapi ada juga sisi negatifnya. Ada bidang yang bergantung pada kenyataan bahwa beberapa masalah sulit diselesaikan, yaitu kriptografi, ilmu tentang sandi. Bisa jadi sandi-sandi yang dipakai saat ini akan jauh lebih mudah dipecahkan.

Selingan: karena kamu sudah membaca sampai sejauh ini, sebagai hadiah saya beri tahu jawaban masalah 3, yaitu 24 + 1 − 60 + 16 − 83 + 48 + 54.

Apa yang terjadi jika P ≠ NP?

Seandainya kelas masalah P dan NP berbeda, tidak banyak yang akan terjadi, karena itu kurang lebih keadaan saat ini. Saat ini kita tidak punya algoritma yang menyelesaikan masalah sulit dari NP dalam waktu polinomial. Seandainya ada yang membuktikan bahwa P ≠ NP, keadaannya akan tetap seperti itu selamanya. Bukti bahwa P = NP akan menjadi sensasi yang jauh lebih besar.

P vs. NP dalam budaya pop

• Dalam salah satu episode serial The Simpsons, Homer masuk ke semacam realitas alternatif dan di sana ia melihat bahwa P = NP. Cuplikannya dapat dilihat di youtube.com.
• Sebaliknya, dalam serial Futurama terlihat sebuah gudang dengan dua map, satu berlabel P dan satu lagi berlabel NP. Cuplikannya dapat dilihat di youtube.com.
• Episode kedua musim kedua serial Elementary, berjudul “Solve for X”, mengisahkan pembunuhan seorang matematikawan yang kemungkinan besar telah memecahkan masalah P versus NP.