T: Apa yang dimaksud dengan Masalah Milenium?
J: Masalah Milenium adalah salah satu masalah matematika yang paling penting dan menantang di abad ini yang membahas masalah apakah setiap masalah yang mudah diverifikasi oleh komputer juga mudah dipecahkan.
T: Bagaimana kita dapat mengklasifikasikan masalah matematika?
J: Masalah matematika dapat diklasifikasikan sebagai masalah P atau NP berdasarkan apakah masalah tersebut dapat dipecahkan dalam waktu polinomial terbatas.
T: Apa perbedaan antara soal P dan NP?
J: Soal P relatif cepat dan "mudah" diselesaikan oleh komputer, sedangkan soal NP cepat dan "mudah" diperiksa oleh komputer, tetapi belum tentu mudah diselesaikan.
T: Siapa yang memperkenalkan masalah P versus NP?
J: Stephen Cook memperkenalkan masalah P versus NP pada tahun 1971 dalam artikelnya "Kompleksitas prosedur pembuktian teorema."
T: Mengapa masalah P versus NP penting?
J: Masalah P versus NP dianggap sebagai masalah terbuka yang paling penting dalam ilmu komputer dan merupakan salah satu dari tujuh Masalah Hadiah Milenium, dengan hadiah $1.000.000 untuk solusi yang mengundang pengakuan yang dipublikasikan oleh Clay Institute dan mungkin solusi yang mengubah keseluruhan matematika.
T: Apakah mungkin untuk menyelesaikan masalah NP-lengkap dalam waktu kuadratik atau linier?
J: Pada tahun 1956, Kurt Gödel menulis surat kepada John von Neumann yang menanyakan apakah suatu masalah NP-complete dapat diselesaikan dalam waktu kuadratik atau linier.
T: Mengapa banyak ahli matematika berharap Masalah Milenium saling berhubungan?
J: Banyak dari Masalah Milenium yang berhubungan dengan masalah-masalah lain, dan ini merupakan impian banyak matematikawan untuk menemukan teori pemersatu.