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