Apa yang mendefinisikan masalah yang sulit? Berdasarkan pertanyaan sebelumnya, tulislah konteks yang berisi jawabannya. Bisa 1 - 20 kalimat. Konteks:
Ini memotivasi konsep masalah yang sulit untuk kelas kompleksitas. Sebuah masalah X sulit untuk kelas masalah C jika setiap masalah dalam C dapat direduksi menjadi X. Dengan demikian tidak ada masalah dalam C lebih sulit dari X, karena algoritma untuk X memungkinkan kita untuk memecahkan masalah dalam C. Tentu saja, gagasan masalah yang sulit tergantung pada jenis pengurangan yang digunakan. Untuk kelas kompleksitas yang lebih besar dari P, pengurangan waktu polinomial biasanya digunakan. Secara khusus, kumpulan masalah yang sulit untuk NP adalah kumpulan masalah NP-hard.