Mi egy másik példa a polinomiális-idő redukciós módszerre? Az előző kérdés alapján írj egy szövegkörnyezetet, amely tartalmazza a választ. Lehet 1 - 20 mondat. A szövegkörnyezet:
A leggyakrabban használt redukció a polinomiális idő redukciója. Ez azt jelenti, hogy a redukciós folyamat polinomiális időt vesz igénybe. Például, egy egész szám négyzetére vetítésének problémája lecsökkenthető két egész szám szorzásának problémájára. Ez azt jelenti, hogy két egész szám szorzásának algoritmusával lehet egy egész számot négyzetre emelni. Valóban, ez úgy történhet meg, hogy a szorzás algoritmus mindkét bemenetének ugyanazt a bemenetet adjuk. Így láthatjuk, hogy a négyzetbe emelés nem nehezebb, mint a szorzás, mivel a négyzetbe emelés a szorzásra redukálható.