תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דוגמא: תקלדה |
|||
שורה 22:
נאמר ששפה <math>L_1</math> '''ניתנת לרדוקציה''' ל־<math>L_2</math> אם קיימת רדוקציה מ־<math>L_1</math> ל־<math>L_2</math>, ונסמן: <math>L_1 \le L_2</math>. המשמעות היא שניתן להמיר קלט עבור הבעיה <math>L_1</math> לקלט מתאים עבור השפה <math>L_2</math>. אם יש לנו "כלי" שמכריע את השפה <math>L_2</math>, אותו כלי יכול לשמש להכרעת <math>L_1</math>.
{{-}}
===דוגמא===
|