Banyak kelas kompleksitas didefinisikan menggunakan konsep reduksi. Reduksi adalah transformasi dari satu masalah ke masalah lain. Ini menangkap gagasan informal tentang masalah yang setidaknya sama sulitnya dengan masalah lain. Misalnya, jika masalah X dapat diselesaikan dengan menggunakan algoritma untuk Y, X tidak lebih sulit daripada Y, dan kami mengatakan bahwa X direduksi menjadi Y. Ada banyak jenis reduksi yang berbeda, berdasarkan metode reduksi, seperti Reduksi masak, reduksi Karp, dan reduksi Levin, dan batasan kompleksitas reduksi, seperti reduksi waktu polinomial atau reduksi ruang log.
Pengurangan pada dasarnya mengambil satu masalah dan mengubahnya menjadi apa?
masalah lain
masalah lain
Pengurangan NNO
pada PPO
dasar NNO
nya PRK
mengambil VBT
satu NUM
masalah NNO
dan CCN
mengubah VBT
nya PRK
menjadi VBI
apa PRI
? PUN