interestingengineering.com
Dalam dunia ilmu komputer yang sarat dengan matematika, seorang pemrogram dapat memprogram satu program komputer untuk memecahkan persoalan secara cepat, contohnya aritmatika dasar, menyortir daftar, dan pencarian melalui tabel data.
Kelompok soal yang dapat dipecahkan algoritme dalam "waktu polinomial" ini disebut "P".
Akan tetapi, ada beberapa pertanyaan yang belum dapat diketahui cara jawab cepatnya. Namun, jika terdapat cukup petunjuk yang mengarah ke jawabannya, adalah hal yang mungkin untuk memverifikasi hasilnya dengan cepat.
Contohnya adalah menghitung faktor prima dari bilangan besar. Jika terdapat daftar bilangannya, mungkin dapat dengan mudah diverifikasi. Namun, tak ada cara pasti untuk mendapatkan faktor-faktor tersebut secara efisien.
Kelompok soal tersebut tidak dapat terjawab secara efisien, namun dapat "diverifikasi" dalam waktu "polinomial non-deterministik", disebut "NP".
youtube.com/hackerdashery
Setiap kelompok soal dalam P secara otomatis juga termasuk NP.
Dengan kata lain, jika kamu dapat memecahkan satu soal dengan cepat (P), berarti solusi-solusi lain dapat kamu cari dengan cara memecahkan soal tersebut untuk memverifikasi apakah jawabannya sesuai dengan hasil solusi-solusi tersebut (NP).
Inti dari "P vs NP" adalah pertanyaan "apakah kebalikannya berlaku?" (apakah soal NP bisa juga diselesaikan dalam P?) Dengan kata lain, jika ada cara efisien untuk memverifikasi solusi untuk satu soal, apakah ada cara efisien untuk benar-benar menemukan solusi soal tersebut?
Sebagian besar matematikawan dan ilmuwan komputer menjawab "tidak". Mereka berpendapat jika ada algoritme yang dapat memecahkan masalah NP selayaknya P, algoritme tersebut akan memiliki implikasi yang mengejutkan di bidang matematika, sains, dan teknologi.
Butuh pengertian tentang ilmu komputer dan matematika yang lebih dalam untuk menjawab pertanyaan P = NP dan sebaliknya, hal yang belum dimiliki bidang teknologi manusia saat ini.