תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ ←‏דוגמא: תקלדה
Gran (שיחה | תרומות)
שורה 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>.
{{-}}
===דוגמא===