תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←מוטיבציה: הגהה |
←הגדרה: איור |
||
שורה 15:
==הגדרה==
[[קובץ:Reduction map.png|שמאל|ממוזער|250px|רדוקציה: כל הקלטים ב־<math>L_1</math> ממופים לקלטים של <math>L_2</math>, ואילו קלטים שאינם ב־<math>L_1</math> ממופים לקלטים שאינם ב־<math>L_2</math>]]
תהיינה <math>L_1, L_2</math> שפות מעל א"ב <math>\Sigma</math>. הפונקציה <math>f: \Sigma^* \to \Sigma^*</math> נקראת '''רדוקציה''' מ־<math>L_1</math> ל־<math>L_2</math> אם מתקיים:
# f היא פונקציה מלאה
# f ניתנת לחישוב
# הרדוקציה <u>תקפה</u>: <math>x\in L_1</math> אם״ם <math>f(x)\in L_2</math>
נאמר ששפה <math>L_1</math> '''ניתנת לרדוקציה''' ל־<math>L_2</math> אם קיימת רדוקציה מ־<math>L_1</math> ל־<math>L_2</math>, ונסמן: <math>L_1 \le L_2</math>.
| |||