Pengurangan yang paling umum digunakan adalah pengurangan waktu polinomial. Ini berarti bahwa proses reduksi memakan waktu polinomial. Misalnya, masalah mengkuadratkan bilangan bulat dapat dikurangi menjadi masalah mengalikan dua bilangan bulat. Ini berarti suatu algoritma untuk mengalikan dua bilangan bulat dapat digunakan untuk mengkuadratkan bilangan bulat. Memang, ini bisa dilakukan dengan memberikan input yang sama ke kedua input dari algoritma multiplikasi. Jadi kita melihat bahwa kuadrat tidak lebih sulit daripada perkalian, karena kuadrat dapat dikurangi menjadi perkalian.
Apa yang tidak perlu tetap konstan dalam algoritma multiplikasi untuk menghasilkan hasil yang sama baik mengalikan atau mengkuadratkan dua bilangan bulat?
memasukkan
input
Apa PRI
yang PRR
tidak NEG
perlu TAME
tetap ADV
konstan ADJ
dalam PPO
algoritma NNO
multiplikasi NNO
untuk PPO
menghasilkan VBT
hasil NNO
yang PRR
sama ADJ
baik ADJ
mengalikan VBT
atau CCN
mengkuadratkan VBT
dua NUM
bilangan NNO
bulat ADJ
? PUN