תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ הגהה |
|||
שורה 5:
<div class="toclimit-3">__TOC__</div>
==דוגמה לרדוקציה ומאפייניה==
נניח שנתנת לנו הבעיה הבאה: נתונה רשימת מספרים, ועלינו למצוא האם האיבר הגדול ביותר מופיע לפחות שלוש פעמים. כמובן שאפשר לפתור זאת בדרכים שונות. עם זאת, נניח שעומדת ברשותנו שגרה המקבלת רשימת מספרים, ומוצאת האם האיבר ה''קטן'' ביותר מופיע ''פחות'' משלוש פעמים. האם נוכל להשתמש בשגרה זו? בודאי. נוכל לעשות זאת באופן הבא:
# נקח את הרשימה המקורית, ונמיר אותה לרשימת המספרים ההפוכים בסימניהם לרשימה המקורית (לדוגמה, הרשימה <math>[1, -3, 4, 2]</math> תהפוך לרשימה <math>[-1, 3,-4, -2]</math>).
# נפעיל את השגרה שכבר קיימת לנו, ונקבל את תוצאתה.
# נחזיר את ההיפך מהתוצאה שהתקבלה.
קל לראות ששיטה זו פותרת את הבעיה החדשה. אמ"ם האיבר הקטן ביותר ברשימה החדשה, נסמנו כ
<math>-y</math>
#לכל קלט יש קלט מומר – ניתן להמיר כל קלט!▼
מופיע פחות משלוש פעמים ברשימה החדשה, אז לא נכון שהמספר הגדול ביותר ברשימה המקורית, y, מופיע לפחות שלוש פעמים ברשימה המקורית.
אפשר לראות שהמרנו בעיה חדשה לבעיה קודמת, לגביה אנו יודעים יותר (במקרה זה, יש כבר שגרה כתובה לה), באופן שמועיל לפתרון. מה מאפיין המרה זו?
#ניתן לבצע את ההמרה ע״י מ״ט – ההמרה ברת־חישוב.
#מפתרון הבעיה הקודמת אפשר להסיק חד-משמעית את הפתרון לבעיה .
הרדוקציה, לכן, ממירה בעיה חדשה לבעיה קודמת שעליה אנו כבר יודעים משהו. בדוגמה זו, מצאנו דרך לפתור בעיה חדשה ע"י המרה לבעיה שפתרונה כבר קיים. אפשר לעשות גם הפוך: בהנתן בעיה, אפשר להראות שלו היה לה פתרון, אז היה גם פתרון לבעיה אחרת שלה ידוע שאין פתרון. בהמשך הפרק נשתמש ברעיון הרדוקציה כדי להמיר בין שפות פורמליות, בעיקר כדי להראות לגבי חלקן שהן אינן כריעות.
==הגדרה==
| |||