מפת הסיבוכיות
EN
יחידה 3

אי־דטרמיניזם ותעודות

חישוב מסתעף, אימות פולינומיאלי ושקילות שתי ההגדרות של NP.

מטרות

  • להגדיר קבלה במכונה אי־דטרמיניסטית.
  • לתרגם בין ענף מקבל לתעודה.
  • לא לבלבל אי־דטרמיניזם עם אקראיות.

אינטואיציה

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

הגדרות פורמליות

מכונה אי־דטרמיניסטית רצה בזמן t(n)t(n) אם כל ענף עוצר בתוך t(n)t(n) צעדים. כמו כן,

NP=⋃k≥1NTIME(nk).\mathrm{NP}=\bigcup_{k\ge1}\mathrm{NTIME}(n^k).

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

באופן כללי,

NTIME(t(n))={L:מכונה אי־דטרמיניסטית מכריעה את L וכל ענף אורכו O(t(n))},\mathrm{NTIME}(t(n))= \{L:\text{מכונה אי־דטרמיניסטית מכריעה את }L \text{ וכל ענף אורכו }O(t(n))\},

ו-NSPACE(s(n))\mathrm{NSPACE}(s(n)) מוגדרת לפי המספר המרבי של תאי עבודה בכל ענף. כל ענף של מכריע חייב לעצור. ענף אינסופי יחיד פוסל חסם זמן, גם אם ענף אחר מקבל מהר.

בנייה מודרכת

עץ חישוב אי־דטרמיניסטי

שלב 1 מתוך 7
φ =(x₁ ∨ ¬x₂)∧(x₂ ∨ x₃)
עץ חישוב לא־דטרמיניסטי בינאריהמאמת מנחש שלוש סיביות השמה. שמונה עלים בודקים את הנוסחה, והמסלול 110 מגיע לעלה מקבל.ε
בחירה בינארית חוקית

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

מוודא פולינומיאלי הוא אלגוריתם VV ופולינום pp שעבורם

x∈L  ⟺  ∃y, (∣y∣≤p(∣x∣)∧V(x,y)=1).x\in L\iff \exists y,\ \bigl(|y|\le p(|x|)\land V(x,y)=1\bigr).

משפט. הגדרת NP באמצעות מכונה אי־דטרמיניסטית שקולה להגדרה באמצעות מוודא ותעודה פולינומיאליים.

מהלך ההוכחה

נראה שני כיוונים. נניח מודל multitape סטנדרטי ומכריעים/מוודאים עוצרים.

כיוון I — מ-NTM למוודא. תהי NN מכונה אי־דטרמיניסטית המכריעה את LL בזמן p(n)p(n). לכל קונפיגורציה יש לכל היותר bb בנים (bb קבוע התלוי ב-NN). מקודדים בחירת מעבר ב-O(1)O(1) ביטים. תעודה yy היא מחרוזת הבחירות לאורך ענף באורך ≤p(∣x∣)\le p(|x|), ולכן ∣y∣≤O(p(∣x∣))|y|\le O(p(|x|)).

המוודא V(x,y)V(x,y) מדמה את NN על xx לפי הבחירות ב-yy: בכל צעד קורא את סימן הבחירה הבא, דוחה אם הבחירה אינה חוקית או אם yy נגמר לפני עצירה, ומקבל רק אם הסימולציה מגיעה למצב מקבל תוך ≤p(∣x∣)\le p(|x|) צעדים. הזמן דטרמיניסטי פולינומיאלי ב-∣x∣+∣y∣|x|+|y|.

שלמות: אם x∈Lx\in L קיים ענף מקבל; קידוד בחירותיו הוא תעודה מתקבלת. נאותות: כל תעודה מתקבלת מתארת ענף חוקי מקבל של NN.

כיוון II — ממוודא ל-NTM. נתון מוודא VV ופולינום qq כך ש-x∈Lx\in L אמ״ם קיים ∣y∣≤q(∣x∣)|y|\le q(|x|) עם V(x,y)=1V(x,y)=1. המכונה NN מנחשת סימן־אחר־סימן מחרוזת באורך ≤q(∣x∣)\le q(|x|), ואז מריצה דטרמיניסטית את VV. אם x∈Lx\in L קיים ניחוש מקבל; אם x∉Lx\notin L כל ניחוש נדחה. חסם האורך חיוני: בלי חסם, גם בדיקה פשוטה של עד מעריכי אינה פולינומיאלית ב-∣x∣|x|.

מה אין כאן. השקילות אינה נותנת סימולציה דטרמיניסטית פולינומיאלית, ואינה קובעת NP=coNP\mathrm{NP}=\mathrm{coNP}.

גודל עץ וסימולציה דטרמיניסטית

אם לכל קונפיגורציה לכל היותר bb בנים וכל ענף באורך t(n)t(n), מספר הצמתים יכול להיות

1+b+⋯+bt(n)=bO(t(n)).1+b+\cdots+b^{t(n)}=b^{O(t(n))}.

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

NTIME(t(n))⊆DTIME(2O(t(n))),\mathrm{NTIME}(t(n))\subseteq\mathrm{DTIME}(2^{O(t(n))}),

ולכן

P⊆NP⊆EXP.\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}.

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

אין להסיק זמן דטרמיניסטי פולינומיאלי מכך שכל ענף פולינומיאלי: עומק העץ אינו מספר צמתיו.

בסימולציית מקום, חיפוש נאיבי עלול לפגוש מחזורים. למכונה המשתמשת ב-s(n)≥log⁡ns(n)\ge\log n מקום יש 2O(s(n))2^{O(s(n))} קונפיגורציות, וקבלה היא נגישות מקונפיגורציית ההתחלה למקבלת. חיפוש דטרמיניסטי ישיר נותן

NSPACE(s(n))⊆DSPACE(2O(s(n))).\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(2^{O(s(n))}).

משפט סביץ' החזק יותר קובע

NSPACE(s(n))⊆DSPACE(s(n)2)\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(s(n)^2)

עבור s(n)≥log⁡ns(n)\ge\log n. לכן NPSPACE=PSPACE\mathrm{NPSPACE}=\mathrm{PSPACE}.

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

דוגמה פתורה

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

אם הקודקודים ממוספרים 1,…,m1,\ldots,m, העד מכיל mm מספרים בני O(log⁡m)O(\log m) ביטים וגודלו O(mlog⁡m)O(m\log m). המוודא בודק טווח, יחידות ו-mm צלעות נדרשות. תעודה משובשת או קודקוד חוזר נדחים.

דוגמת SAT. עבור נוסחה φ\varphi במשתנים z1,…,zmz_1,\ldots,z_m, מנחשים mm ביטים ומעריכים את עץ התחביר. אם הנוסחה ספיקה, ענף ההשמה המספקת מקבל; אם ענף מקבל, הביטים שלו מתארים השמה מספקת. זהו קיום, לא ניסוי אקראי.

ריפוד אי־דטרמיניסטי

עבור

Pad⁡p(L)={x#1p(∣x∣)−∣x∣:x∈L},\operatorname{Pad}_p(L)= \{x\#1^{p(|x|)-|x|}:x\in L\},

אותו יחס אורכים חל על NTIME\mathrm{NTIME} ו-NSPACE\mathrm{NSPACE}. אם ל-LL יש מכריע אי־דטרמיניסטי בזמן 2O(n)2^{O(n)} ו-p(n)=2Θ(n)p(n)=2^{\Theta(n)}, אז הגרסה המרופדת ניתנת להכרעה אי־דטרמיניסטית בזמן פולינומיאלי באורך הכולל N=p(n)N=p(n).

תחילה יש לוודא את צורת הריפוד ולחלץ את xx, ואז לדמות. כל ענף מדומה חייב לעמוד בחסם המתורגם. הריפוד יוצר שפה חדשה ואינו מוכיח שה-LL המקורית ב-NP\mathrm{NP}. בטיעון מותנה יש לציין במפורש את nn, את NN, ואת שימור תנאי הקבלה הקיומי.

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

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

הצעת המחשה

להציג עץ חישוב עם עלה מקבל יחיד ולהמיר את תוויות הקשתות במסלולו למחרוזת תעודה.

תרגילים

תרגיל 1 — סמנטיקת קבלה ודחייה

הגדירו מתי NTM מקבלת קלט xx ומתי היא דוחה אותו (כמכריע). הוכיחו כי החלפת מצבי קבלה ודחייה אינה נותנת בהכרח מכריע ל-L‾\overline L.

פתרון

הגדרה. NN מקבלת xx אם קיים ענף חישוב מקבל. כמכריע בזמן tt, כל ענף עוצר תוך t(∣x∣)t(|x|) צעדים, ו-x∉Lx\notin L אמ״ם כל הענפים דוחים.

החלפה. לאחר החלפת מצבי קבלה/דחייה, הקבלה החדשה היא ״קיים ענף שהיה דוחה״ — כמת קיום — בעוד ש-L‾\overline L דורש ״אין ענף מקבל״, כלומר תנאי אוניברסלי על כל הענפים. הכמתים אינם מתחלפים בהחלפה מקומית של מצבי עצירה.

תרגיל 2 — תעודה כמחרוזת בחירות

הוכיחו כי אם L∈NTIME(p(n))L\in\mathrm{NTIME}(p(n)) אז קיים מוודא דטרמיניסטי פולינומיאלי עם תעודות באורך O(p(n))O(p(n)). ציינו שלמות ונאותות.

פתרון

מקודדים את בחירות המעבר לאורך ענף באורך ≤p(n)\le p(n) ב-O(1)O(1) ביטים לצעד. המוודא מדמה לפי yy ודוחה בחירה לא חוקית. שלמות: ענף מקבל נותן תעודה. נאותות: תעודה מתקבלת = ענף מקבל אמיתי. הזמן O(p(n))O(p(n)).

תרגיל 3 — עומק פולינום אינו P\mathrm P

הוכיחו כי מכונה בינארית עם ענפים באורך n3n^3 עשויה ליצור 2Θ(n3)2^{\Theta(n^3)} צמתים בעץ, והסיקו מדוע סימולציה דטרמיניסטית נאיבית אינה מוכיחה NP⊆P\mathrm{NP}\subseteq\mathrm P.

פתרון

בעץ מלא בינארי בעומק t=n3t=n^3 יש 2t+1−1=2Θ(n3)2^{t+1}-1=2^{\Theta(n^3)} צמתים. מנייה דטרמיניסטית דורשת זמן מעריכי. ההכלה הידועה היא NTIME(t)⊆DTIME(2O(t))\mathrm{NTIME}(t)\subseteq\mathrm{DTIME}(2^{O(t)}), לא פולינומיאלית.

תרגיל 4 — מדידת מקום אי־דטרמיניסטי

הגדירו sN(n)s_N(n) למכונה אי־דטרמיניסטית. הוכיחו כי ״קיים ענף המשתמש מעט מקום״ אינו שקול להגדרת NSPACE\mathrm{NSPACE}.

פתרון

sN(n)s_N(n) הוא המקסימום, על פני כל הענפים, של מספר תאי העבודה שבהם ביקרו. NSPACE(s)\mathrm{NSPACE}(s) דורש שכל ענף יישאר בתוך s(n)s(n) תאים. קיום ענף חסכוני בלבד מאפשר ענפים חורגים ״מוסתרים״ מאחורי ענף מקבל — וזה אינו ההגדרה.

תרגיל 5 — סביץ' ו-NPSPACE\mathrm{NPSPACE}

נסחו את מסקנת משפט סביץ' עבור s(n)≥log⁡ns(n)\ge\log n בת־בנייה, והסיקו NPSPACE=PSPACE\mathrm{NPSPACE}=\mathrm{PSPACE}.

פתרון

סביץ': NSPACE(s(n))⊆DSPACE(O(s(n)2))\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(O(s(n)^2)). ל-s(n)=nks(n)=n^k מתקבל NSPACE(nk)⊆DSPACE(n2k)⊆PSPACE\mathrm{NSPACE}(n^k)\subseteq\mathrm{DSPACE}(n^{2k})\subseteq\mathrm{PSPACE}. האיחוד נותן NPSPACE⊆PSPACE\mathrm{NPSPACE}\subseteq\mathrm{PSPACE}. ההכלה ההפוכה מיידית, ולכן שוויון.

סיכום

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

תרגול מודרך

משימה 1 — מוודא לקליקה

בנו מוודא פולינומיאלי ל-CLIQUE. הוכיחו שלמות, נאותות וחסם אורך התעודה.

פתרון

תעודה: kk מזהי קודקודים. בדיקות: בטווח, שונים, וכל (k2)\binom{k}{2} זוגות הם צלעות. אורך O(klog⁡∣V∣)O(k\log|V|), זמן פולינומיאלי בקידוד. שלמות: קליקה אמיתית נותנת רשימה. נאותות: רשימה מתקבלת היא קליקה. האמירה ״ננחש ונאשר״ בלי בדיקות אינה הוכחה.

משימה 2 — מלכודת המשלים

הסבירו מדוע לא ניתן להכריע את L‾\overline L על ידי החלפת עלי קבלה/דחייה בעץ של מכונה ל-LL. מה הקשר ל-NP\mathrm{NP} מול coNP\mathrm{coNP}?

פתרון

דחייה מקורית = כל הענפים דוחים. לאחר החלפה, די בענף מקורי דוחה אחד לקבלה — תנאי חלש. NP\mathrm{NP} הוא ∃\exists-ראיה; coNP\mathrm{coNP} הוא ∀\forall/ראיית־לא. השאלה האם הם שווים פתוחה.

משימה 3 — מסלול פשוט באורך kk

תארו את בעיית ״מסלול פשוט באורך ≥k\ge k״ בשלושה אופנים (NTM, מוודא, עץ) והוכיחו שייכות ל-NP\mathrm{NP}. מה סימולציה דטרמיניסטית נותנת?

פתרון

מנחשים/מקבלים כתעודה רצף k+1k+1 קודקודים; בודקים חוקיות, היעדר חזרות וצלעות. אורך O(klog⁡∣V∣)O(k\log|V|); אם k>∣V∣k>|V| דוחים. שלושת התיאורים הם אותו ∃\exists. מנייה דטרמיניסטית: ∣V∣k+1=2O(klog⁡∣V∣)|V|^{k+1}=2^{O(k\log|V|)} — מעריכי, לא הוכחת P\mathrm P.

מקורות

  • ראיית סיכום סטודנטים: הסיכום הממוזג, עמ' 25-42; עמ' 50-54 מצוטטים רק במקום שבו החומר חופף לטבלאות חישוב. הסיכום משמש להתאמת התוכן בלבד.
  • ראיית קורס: תמלילי סמסטר א' 2026, שיעורים 5-6, לאי־דטרמיניזם ולריפוד.
  • אימות: Sipser, מהדורה 3, עמ' 292-304 ו-321-330.
  • אימות: Arora-Barak, טיוטה, עמ' 43-64 ו-83-88.
  • אימות: Papadimitriou, עמ' 35-51 ו-159-170.

העמודים שמהם זה נכתב

1 עמודים

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