Pertanyaan apakah P sama dengan NP adalah salah satu pertanyaan terbuka paling penting dalam ilmu komputer teoretis karena implikasi yang luas dari suatu solusi. Jika jawabannya adalah ya, banyak masalah penting dapat terbukti memiliki solusi yang lebih efisien. Ini termasuk berbagai jenis masalah pemrograman bilangan bulat dalam penelitian operasi, banyak masalah dalam logistik, prediksi struktur protein dalam biologi, dan kemampuan untuk menemukan bukti formal teorema matematika murni. Masalah P versus NP adalah salah satu Masalah Hadiah Milenium yang diusulkan oleh Clay Mathematics Institute. Ada hadiah US $ 1.000.000 untuk menyelesaikan masalah.
Jika P pada akhirnya terbukti sama dengan NP total, apa efeknya pada efisiensi masalah?
solusi yang lebih efisien
solusi yang lebih efisien
Jika CSN
P NNP
pada PPO
akhirnya ADV
terbukti VBP
sama ADJ
dengan PPO
NP NNP
total ADJ
, PUN
apa PRI
efek NNO
nya PRK
pada PPO
efisiensi NNO
masalah NNO
? PUN