רדוקציות חישוביות

רדוקציות מיפוי המשמשות בחישוביות: כל פונקציה כריעה מספיקה (ללא חסם זמן פולינומיאלי). אלו מעבירות כריעות וזיהוי — אם A ≤m B ו־B כריעה, גם A כריעה; אם A ≤m B ו־A אינה כריעה, גם B אינה כריעה.