Dalam teori kompleksitas komputasi, adalah kelas masalah informal "setidaknya sebagai keras sebagai masalah di NP." Masalah H NP-sulit jika dan hanya jika ada NP-lengkap masalah L yang waktunya polinomial Turing boleh untuk H. L dengan kata lain, dapat diselesaikan dalam waktu polinomial dengan oracle mesin dengan oracle untuk H. informal kita dapat memikirkan suatu algoritma yang dapat memanggil seperti oracle mesin sebagai subrutin untuk memecahkan H, dan memecahkan L waktu polinomial jika panggilan subrutin mengambil hanya satu langkah untuk menghitung. NP-keras masalah mungkin jenis apapun: keputusan Cari masalah, masalah-masalah optimasi.