Masalah P versus NP

Istilah informal "dengan cepat", yang digunakan di atas, berarti adanya algoritme yang memecahkan tugas yang berjalan dalam waktu polinom, sehingga waktu untuk menyelesaikan tugas bervariasi sebagai fungsi polinom pada ukuran input ke algoritme (berlawanan dengan, katakanlah, waktu eksponensial). Kelas umum pertanyaan yang beberapa algoritmanya dapat memberikan jawaban dalam waktu polinomial disebut "kelas P" atau hanya "P". Untuk beberapa pertanyaan, tidak ada cara yang diketahui untuk menemukan jawaban dengan cepat, namun jika ada informasi yang menunjukkan jawabannya, mungkin untuk memverifikasi jawabannya dengan cepat. Kelas pertanyaan yang jawabannya dapat " diverifikasi " dalam waktu polinom disebut NP, yang berarti "waktu polinomial nondeterministik".