תורת החישוביות/כריעות שפות/רדוקציה חישובית/ארגז חול

בקיום שפות לא כריעות ראינו שבעייה ספיציפית, בעיית העצירה, איננה כריעה, וראינו משיקולי מניה שיש אינספור שפות שאינן אפילו כריעות למחצה. לעתים רוצים להוכיח קיום (או שלילת-קיום) רמת כריעות כלשהי של שפה כלשהי. במצב כזה, אין טעם "להוכיח את הגלגל מחדש" ולבנות סתירה כפי שעשינו בהוכחת אי-כריעותה של בעיית העצירה. במקום זאת, כדאי לבנות על מה שכבר ידוע. נציג כאן את רעיון הרדוקציה שהינו אחד הרעיונות המרכזיים ביותר במדעי המחשב. הרעיון שעומד מאחורי הרדוקציה הוא המרת בעיה אחת לבעיה קודמת, ידועה יותר.

דוגמה לרדוקציה ומאפייניה

נניח שנתנת לנו הבעיה הבאה: נתונה רשימת מספרים, ועלינו למצוא האם האיבר הגדול ביותר מופיע לפחות שלוש פעמים. כמובן שאפשר לפתור זאת בדרכים שונות. עם זאת, נניח שעומדת ברשותנו שגרה המקבלת רשימת מספרים, ומוצאת האם האיבר הקטן ביותר מופיע לפחות שלוש פעמים. האם נוכל להשתמש בשגרה זו? בודאי. נוכל לעשות זאת באופן הבא:

1. נקח את הרשימה המקורית, ונמיר אותה לרשימת המספרים ההפוכים בסימניהם לרשימה המקורית (לדוגמה, הרשימה $[1,-3,4,2]$ תהפוך לרשימה $[-1,3,-4,-2]$).
2. נפעיל את השגרה שכבר קיימת לנו, ונחזיר את תוצאתה.

קל לראות ששיטה זו פותרת את הבעיה החדשה. אם"ם האיבר הקטן ביותר ברשימה החדשה, נסמנו כ $-y$ מופיע לפחות שלוש פעמים ברשימה החדשה, אז המספר הגדול ביותר ברשימה המקורית, y, מופיע לפחות שלוש פעמים ברשימה המקורית.

אפשר לראות שהמרנו בעיה חדשה לבעיה קודמת, לגביה אנו יודעים יותר (במקרה זה, יש כבר שגרה כתובה לה), באופן שמועיל לפתרון. מה מאפיין המרה זו?

1. לכל קלט לבעיה המקורית יש קלט מומר לבעיה הקודמת – ניתן להמיר כל קלט.
2. ניתן לבצע את ההמרה ע״י מ״ט – ההמרה ברת־חישוב.
3. מפתרון הבעיה הקודמת אפשר להסיק חד-משמעית את הפתרון לבעיה .

הרדוקציה, לכן, ממירה בעיה חדשה לבעיה קודמת שעליה אנו כבר יודעים משהו. בדוגמה זו, מצאנו דרך לפתור בעיה חדשה ע"י המרה לבעיה שפתרונה כבר קיים. אפשר לעשות גם הפוך: בהנתן בעיה, אפשר להראות שלו היה לה פתרון, אז היה גם פתרון לבעיה אחרת שלה ידוע שאין פתרון. בהמשך הפרק נשתמש ברעיון הרדוקציה כדי להמיר בין שפות פורמליות, בעיקר כדי להראות לגבי חלקן שהן אינן כריעות.

רדוקציות בין שפות

רדוקציה: כל הקלטים ב־$L_1$ ממופים לקלטים של $L_2$, ואילו קלטים שאינם ב־$L_1$ ממופים לקלטים שאינם ב־$L_2$

תבנית:מבנה תבנית המשמעות היא שניתן להמיר קלט עבור הבעיה $L_1$ לקלט מתאים עבור השפה $L_2$. אם יש לנו "כלי" שמכריע את השפה $L_2$, אותו כלי יכול לשמש להכרעת $L_1$. תבנית:-

תבנית:מבנה תבנית

תבנית:מבנה תבנית

תכונות בסיסיות של רדוקציות

1. לכל שפה L, מתקיים $L\le L$ ע״י פונקציית הזהות.
2. אם f היא רדוקציה מ־$L_1$ ל־$L_2$, ו־g היא רדוקציה מ־$L_2$ ל־$L_3$, אזי ההרכבה $g\circ f$ היא רדוקציה מ־$L_1$ ל־$L_3$. (זוהי תכונת טרנזיטיביות)

$L_1\le L_2,L_2\le L_3\Rightarrow L_1\le L_3$

1. אם f היא רדוקציה מ־$L_1$ ל־$L_2$ אז אותה הפונקציה f היא גם רדוקציה מ־$\overline{L_1}$ ל־$\overline{L_2}$. (נובע מהגדרת הרדוקציה)

משפטים

במילים אחרות, אם השפה $L_2$ שייכת למחלקה כלשהי, גם השפה $L_1$ שייכת לאותה מחלקה. באופן אינטואיטיבי, העובדה ש־$L_2$ שייכת למחלקה מסויימת משמעותה שקיימת מ״ט מסויימת (לפי ההגדרה המתאימה של המחלקה) שמכריעה אותה. עקב קיומה של פונקצית הרדוקציה, ניתן לבנות מ״ט שראשית ממירה קלט של $L_1$ לקלט של $L_2$ (ע״י חישוב הפונקציה f), ואח״כ מריצה את המכונה של $L_2$ על מנת לפתור את הבעיה $L_1$. כעת נוכיח רעיון זה באופן פורמלי: תבנית:הוכחה

ההוכחות עבור סעיפים 2 ו־3 דומות להוכחה לעיל. במקרה זה ייתכן ש־$M_2$ לא עוצרת על קלטים מסויימים, וגם $M_1$ לא תעצור על אותם הקלטים. אבל אלו יהיו בדיוק הקלטים עליהם מותר ל־$M_1$ לא לעצור, לפי ההגדרה המתאימה של $RE$, $coRE$.

אם נביט במשפט ההפכי למשפט הרדוקציה לעיל, נקבל את המשפט הבא: תבנית:משפט

הסבר: נניח ש־$L_1\notin R$. אם $L_2\in R$ נובע ממשפט הרדוקציה שהוכחנו לעיל שגם $L_1\in R$, וזו סתירה.

משפט זה שימושי ביותר להראות ששפות אינן כריעות. מספיק להוכיח ששפה מסויימת $L_1$ אינה כריעה (כלומר, אינה ב־R), ובעזרתה נוכל להוכיח ששפות אחרות אינן כריעות ע״י רדוקציה מ־$L_1$ אל אותן השפות. בד״כ ביצוע רדוקציה היא פעולה פשוטה בהרבה מאשר הוכחה ישירה ששפה אינה כריעה.

להלן מספר דוגמאות להוכחת אי כריעותן של מספר שפות שראינו בכריעות למחצה חיובית.

תבנית:מבנה תבנית