הגדרה פורמלית

הרעיון : דרך לתרגם בעיה אחת לבעיה אחרת. ההוכחות בבעיית האימות נעשו ברדוקציה.

הגדרה:  יהיו   1*A Í å ,   2*B Í å שפות

רדוקצית התאמה מ -A ל B- הינה הפונקציה: 2* å ® 1* å f:  כך שלכל,  1 *,  XÎå                   f(X) ÎB  Û    XÎ A.

מתקיים אם B כריעה וקיימת רדוקצית התאמה מ- A ל- B שניתנת לחישוב אז גם A כריעה.

אנחנו רצינו להראות שאם Hany כרעיה אז גם H כריעה. בצענו רדוקציה מ – H ל- Hany הרדוקציה הייתה הפונקציה COMBINE . COMBINE(P,W) =PW כך ש-  H Î(P,W) Û

PW Î Hany. בדרך כלל השימוש ברדוקציה הוא בדרך השלילה כלומר בהינתן שפה

 A לא כריעה ורדוקציה ניתנת לחישוב מ- A ל B אז גם B לא כריעה.