Ý nghĩa của việc giảm không gian đa thức là gì?
Phép rút gọn được sử dụng phổ biến nhất là phép rút gọn thời gian đa thức. Điều này có nghĩa là quá trình rút gọn mất thời gian đa thức. Ví dụ, bài toán bình phương một số nguyên có thể được rút gọn thành bài toán nhân hai số nguyên. Điều này có nghĩa là một thuật toán nhân hai số nguyên có thể được sử dụng để bình phương một số nguyên. Thật vậy, điều này có thể được thực hiện bằng cách đưa cùng một đầu vào cho cả hai đầu vào của thuật toán nhân. Do đó, chúng ta thấy rằng bình phương không khó hơn phép nhân, vì bình phương có thể được rút gọn thành phép nhân.