מהי דוגמה נוספת לשיטת הפחתת זמן פולינומי? בהתחשב בשאלה הקודמת, כתוב את ההקשר שמכיל את התשובה. זה יכול להיות 1 - 20 משפטים. -הקשר:
הפחתה הנפוצה ביותר היא הפחתה בזמן פולינומי. זה אומר שהתהליך של הפחתה לוקח זמן פולינומי. לדוגמה, אפשר להפחית את בעיית הריבוע של מספר שלם לבעיית הכפלת שני מספרים שלמים. זה אומר שאפשר להשתמש באלגוריתם להכפיל שני מספרים שלמים כדי להעלות מספר שלם בריבוע. אכן, זה יכול להיעשות על ידי מתן אותה קלט לשתי הקלטות של אלגוריתם הכפל. כך אנו רואים כי הריבוע אינו קשה יותר מאשר הכפלת, שכן הריבוע ניתן להפחית להכפלת.