Banyak kelas yang rumit didefinisikan menggunakan konsep pengurangan. Pengurangan adalah perubahan dari satu masalah menjadi masalah lain. Ini menangkap gagasan informal tentang masalah yang paling tidak sulit sebagai masalah lain. Sebagai contoh, jika masalah X dapat diselesaikan menggunakan algoritma untuk Y, X tidak lebih sulit daripada Y, dan kita mengatakan bahwa X mengurangi ke Y. Ada banyak jenis pengurangan, berdasarkan metode pengurangan, seperti pengurangan Cook, pengurangan Karp dan pengurangan Levin, dan terikat pada kompleksitas pengurangan, seperti pengurangan polinomial-time atau pengurangan log-space.
Apa enam jenis pengurangan?
pengurangan Cook, pengurangan Karp dan pengurangan Levin, dan terikat pada kompleksitas pengurangan, seperti pengurangan polinomial-time atau