הוכחת שקילות שתי ההגדרות של NP

מעבר בין זמן אי־דטרמיניסטי פולינומי לבין תעודות חסומות פולינומית.

שאלה

הוכיחו ששפה $L$ מוכרעת על ידי מכונת טיורינג אי־דטרמיניסטית בזמן פולינומי אם ורק אם קיימים פולינום $p$ ומוודא דטרמיניסטי פולינומי $V$ כך ש-

עקבו אחר אורך התעודה וזמן האימות בשני הכיוונים.

דרישות קדם

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

רמז 1

קודדו בחירה אי־דטרמיניסטית אחת לכל צעד.

רמז 2

דחו תעודות שאינן מתארות חישוב חוקי ומקבל.

רמז 3

בכיוון ההפוך נחשו תעודה חסומה ואז הריצו את $V$.

פתרון מלא

נניח תחילה שמכונה אי־דטרמיניסטית $N$ מכריעה את $L$ וכל ענף עוצר בתוך $q(n)$ צעדים. ליחס המעברים יש מספר קבוע $b$ של אפשרויות בכל צעד. נקודד ענף במחרוזת $y$ באורך $q(n)\lceil\log b\rceil$, עם ריפוד לאחר עצירה מוקדמת. המוודא $V$ מדמה את $N(x)$ דטרמיניסטית ומשתמש בבלוקים של $y$ לבחירת המעבר הבא. הוא דוחה בחירה לא חוקית, ענף דוחה או ענף שלא קיבל לפני השעון.

אורך התעודה $O(q(n))$ וזמן הסימולציה פולינומי. קיים ענף מקבל בדיוק כאשר קיימת מחרוזת בחירות שהמוודא מקבל, ולכן מתקבלת נוסחת הקיום.

בכיוון ההפוך נניח שקיימים $V,p$. המכונה האי־דטרמיניסטית מנחשת תעודה באורך לכל היותר $p(n)$ ומריצה את $V(x,y)$. אפשר לנחש אורך קבוע $p(n)$ עם סימן ריפוד ולבדוק שהריפוד תקני. אם זמן המוודא הוא $r(|x|+|y|)$, הזמן הכולל חסום ב-

שהוא פולינומי. כל הענפים עוצרים.

אם $x\in L$, ענף אחד מנחש עד חוקי ומקבל. אם $x\notin L$, שום עד אינו גורם לקבלה ולכן כל הענפים דוחים. סדר הכמתים חיוני: די בענף מקבל אחד עבור מופע כן, אך כל הענפים חייבים לדחות מופע לא. המוודא אינו נדרש למצוא עד, אין דרישת יחידות, והוא חייב לעצור גם על תעודות פגומות או ארוכות מדי.

נקודות בדיקה

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

טעויות נפוצות

• אי־חסימת אורך קידוד החישוב.
• דרישת ענף דוחה אחד בלבד למופע לא.
• מדידת זמן לפי הערך המספרי ולא אורך הקלט.

מקורות ואימות

• Merged summary, pp. 40-42
• 2026 transcript 8
• Sipser 3e, sec. 7.3
• Arora-Barak draft, sec. 2.1
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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

פתיחה בגלריית ההמחשות: עץ חישוב אי־דטרמיניסטי