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

NP ו-coNP

תעודות פולינומיאליות, שקילותן לחישוב אי־דטרמיניסטי ואי־הסימטריה בין ראיות NP ו-coNP.

מטרות

  • לעבור בשני הכיוונים בין הגדרת NP באמצעות מכונה אי־דטרמיניסטית לבין הגדרתה באמצעות מוודא.
  • להסביר מדוע גם אורך התעודה וגם זמן האימות חייבים להיות חסומים פולינומיאלית.
  • לפרש coNP כראיה קצרה לטענת ״לא״ או לטענה אוניברסלית, בלי לזהותה עם ״כל מה שאינו ב-NP״.
  • להוכיח את ההכלות הידועות ולהפריד ביניהן לבין שאלות פתוחות.

1. NP: חיפוש לעומת אימות

לבעיות רבות ב-NP יש צורה ״האם קיים עצם קטן בעל תכונה הניתנת לבדיקה יעילה?״ ב-SAT העצם הוא השמה; ב-CLIQUE הוא אוסף קודקודים; וב-Hamiltonian Cycle הוא סדר הקודקודים. חיפוש דטרמיניסטי עלול לבדוק מספר מעריכי של מועמדים, אך בדיקת מועמד נתון קצרה.

NP אינה קיצור של “not polynomial”, ואינה קביעה שלפיה בעיה כלשהי דורשת זמן מעריכי.

הגדרת המכונה

מכונת טיורינג אי־דטרמיניסטית NN מקבלת xx אם קיים ענף חישוב מקבל. היא מכריעה בזמן p(n)p(n) אם כל ענף נעצר בתוך p(∣x∣)p(|x|) צעדים ו-

x∈L  ⟺  קיים ענף מקבל של N(x).x\in L\iff\text{קיים ענף מקבל של }N(x).

לכן

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

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

הגדרת המוודא

שפה LL שייכת ל-NP אם קיימים פולינומים p,qp,q ומכונה דטרמיניסטית VV כך שלכל xx,

x∈L  ⟺  ∃w, ∣w∣≤p(∣x∣) וגם V(x,w)=1,x\in L \iff \exists w,\ |w|\le p(|x|)\text{ וגם }V(x,w)=1,

ו-VV נעצרת בתוך q(∣x∣+∣w∣)q(|x|+|w|) צעדים. ww היא תעודה. אפשר לדרוש אורך מדויק p(∣x∣)p(|x|) באמצעות ריפוד מוסכם.

החסם על ∣w∣|w| מהותי: אם התעודה מעריכית, אפילו קריאתה אינה פולינומיאלית ב-∣x∣|x|. זמן המוודא נמדד בקלט המלא, אך

q(∣x∣+∣w∣)≤q(∣x∣+p(∣x∣))q(|x|+|w|)\le q(|x|+p(|x|))

הוא פולינום בגודל המופע.

בנייה מודרכת

NP ו־coNP

שלב 1 מתוך 6
ידוע: P⊆NP
הכלות ידועות בין P, NP ו־coNPגבולות סכמטיים ומקווקווים של NP ו־coNP חופפים. P מוכלת בחיתוך שלהם. SAT ו־UNSAT מדגימות שיוכי תעודות ידועים, ואילו P מול NP ו־NP מול coNP נשארות שאלות פתוחות.NPתעודות כן קצרות
גבול סכמטי של מחלקה

2. שקילות מוודא ומכונה אי־דטרמיניסטית

משפט. שפה מוכרעת בידי NTM בזמן פולינומיאלי אם ורק אם יש לה תעודות באורך פולינומיאלי הנבדקות בזמן פולינומיאלי.

מ-NTM למוודא

נניח שכל ענף של N(x)N(x) נמשך לכל היותר c∣x∣dc|x|^d צעדים. התעודה מקודדת את הבחירה האי־דטרמיניסטית בכל צעד בענף מקבל. למכונה קבועה יש מספר קבוע של אפשרויות מעבר, ולכן כל בחירה דורשת מספר קבוע של ביטים, וכל התמליל באורך פולינומיאלי.

V(x,w)V(x,w) מדמה את N(x)N(x) דטרמיניסטית וכופה בכל הסתעפות את הבחירה הרשומה ב-ww. היא דוחה בחירה לא חוקית, תמליל שנקטע, או ענף שאינו מקבל.

  • אם x∈Lx\in L, קיים ענף מקבל והתמליל שלו מתקבל.
  • אם x∉Lx\notin L, אין ענף מקבל, ולכן שום תמליל לא יתקבל.
  • אורך ההדמיה פולינומיאלי.

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

ממוודא ל-NTM

בהינתן V,pV,p, המכונה מחשבת p(∣x∣)p(|x|), מנחשת אי־דטרמיניסטית את ביטי ww, ומריצה V(x,w)V(x,w). אם x∈Lx\in L, ענף אחד מנחש תעודה טובה. אם x∉Lx\notin L, כל התעודות נדחות. הזמן הוא

p(∣x∣)+q(∣x∣+p(∣x∣)),p(|x|)+q(|x|+p(|x|)),

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

3. דוגמאות לתעודות

SAT

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

(x1∨¬x2)∧(x2∨x3),(x_1\lor\neg x_2)\land(x_2\lor x_3),

ההשמה (1,1,0)(1,1,0) היא תעודה: הפסוקית הראשונה נכונה בזכות x1x_1 והשנייה בזכות x2x_2. תעודה גרועה אינה הוכחה למופע לא.

CLIQUE

המופע הוא (G,k)(G,k). התעודה מפרטת kk קודקודים שונים; בודקים טווח, שונות וכל (k2)\binom k2 הצלעות. אם k>∣V∣k>|V|, דוחים מיד. בדיקה זו חשובה כאשר kk מקודד בינרית: אין לבצע kk איטרציות לפני שמגבילים אותו בגודל הגרף.

COMPOSITE

למספר בינרי NN, גורמים 1<a,b<N1<a,b<N עם ab=Nab=N הם תעודה. אורכם O(log⁡N)O(\log N) וכפל ארוך פולינומיאלי באורך הבינרי. זו תעודה ל-COMPOSITE, לא תעודה אוטומטית ל-PRIMES.

4. משלים וראיות coNP

לשפה L⊆{0,1}∗L\subseteq\{0,1\}^* נגדיר

L‾={0,1}∗∖L,coNP={L:L‾∈NP}.\overline L=\{0,1\}^*\setminus L, \qquad \mathrm{coNP}=\{L:\overline L\in\mathrm{NP}\}.

coNP היא מחלקת שפות, לא המשלים הקבוצתי של אוסף השפות NP. שפה יכולה להשתייך לשתיהן.

באמצעות הפיכת תשובת המוודא מתקבלת הצורה

L∈coNP  ⟺  ∃V,p  ∀x:x∈L  ⟺  ∀w, ∣w∣≤p(∣x∣):V(x,w)=1.L\in\mathrm{coNP} \iff \exists V,p\;\forall x: \quad x\in L\iff \forall w,\ |w|\le p(|x|):V(x,w)=1.

באופן שקול, אם x∉Lx\notin L, קיימת תעודה קצרה החושפת זאת. לכן coNP מתארת לעיתים ראיות קצרות לתשובת לא.

TAUT מכילה נוסחאות הנכונות בכל השמה. נוסחה שאינה טאוטולוגיה מגיעה עם השמה מפריכה, ולכן TAUT∈coNP\mathrm{TAUT}\in\mathrm{coNP}. בדומה, UNSAT∈coNP\mathrm{UNSAT}\in\mathrm{coNP} כי המשלימה שלה היא SAT. השמה מספקת אחת מוכיחה SAT; בדיקת כמה השמות שנכשלו אינה מוכיחה UNSAT.

PRIMES נמצאת ב-P, ולכן גם ב-NP וגם ב-coNP. הדוגמה מדגישה שהחיתוך אינו ידוע כשווה ל-P מתוך ההגדרות בלבד.

5. הכלות ותוצאות מותנות

טענה. P⊆NP∩coNP\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}.

מכונה דטרמיניסטית היא NTM בעלת ענף יחיד, ולכן P⊆NP\mathrm P\subseteq\mathrm{NP}. אם L∈PL\in\mathrm P, מחליפים במכריע הכולל קבלה ודחייה ומקבלים מכריע פולינומיאלי ל-L‾\overline L. לכן L∈coNPL\in\mathrm{coNP}.

טענה. אם P=NP\mathrm P=\mathrm{NP}, אז NP=coNP\mathrm{NP}=\mathrm{coNP}.

P סגורה למשלים. אם NP=P, גם NP סגורה למשלים, ולכן L∈NPL\in\mathrm{NP} אם ורק אם L‾∈NP\overline L\in\mathrm{NP}, כלומר L∈coNPL\in\mathrm{coNP}.

לא ידוע אם P≠NP\mathrm P\ne\mathrm{NP} ולא ידוע אם NP≠coNP\mathrm{NP}\ne\mathrm{coNP}. אם שפה NP-שלמה כלשהי נמצאת ב-coNP, אז סגירות כלפי מטה ברדוקציות נותנת NP⊆coNP\mathrm{NP}\subseteq\mathrm{coNP}, ומשלים נותן שוויון.

6. קידודים

שפה היא אוסף מחרוזות. לכן יש להגדיר קידוד ולדחות, בדרך כלל, קלט פגום. מספר בינרי kk תופס Θ(log⁡k)\Theta(\log k) ביטים; לולאה בת kk צעדים עלולה להיות מעריכית באורך הקלט. ״פעולה אחת על מספר״ אינה בהכרח פעולה בזמן קבוע.

7. שלוש תבניות כמתים

לפני שמחפשים תעודה כדאי לכתוב את המבנה הלוגי:

φ∈SAT  ⟺  ∃α  [α מספקת את φ],φ∈TAUT  ⟺  ∀α  [α מספקת את φ],φ∈UNSAT  ⟺  ∀α  [α אינה מספקת את φ].\begin{aligned} \varphi\in\mathrm{SAT} &\iff \exists\alpha\;[\alpha\text{ מספקת את }\varphi],\\ \varphi\in\mathrm{TAUT} &\iff \forall\alpha\;[\alpha\text{ מספקת את }\varphi],\\ \varphi\in\mathrm{UNSAT} &\iff \forall\alpha\;[\alpha\text{ אינה מספקת את }\varphi]. \end{aligned}

הנשוא שבסוגריים נבדק בזמן פולינומיאלי. השורה הראשונה היא ישירות בצורת מוודא NP. בשתי האחרות אי־שייכות נחשפת באמצעות דוגמה נגדית קיומית, ולכן הן בצורת coNP. ההבדל מסביר את אי־הסימטריה בלי לטעון להפרדה: ייתכן שקיימות תעודות פולינומיאליות מתוחכמות ל-UNSAT שאינן פשוט רשימת כל ההשמות. הוכחה שלכל שפת coNP יש תעודות NP תהיה בדיוק הוכחת NP=coNP\mathrm{NP}=\mathrm{coNP}.

אותו מבנה מופיע בגרפים. קבוצה מוצעת של kk קודקודים מוכיחה CLIQUE בבדיקה זוגית. לעומת זאת, ״אין בגרף קליקה בגודל kk״ נראית כטענה על כל תתי־הקבוצות. שפת NO-CLIQUE נמצאת ב-coNP כי קליקה אחת מפריכה אותה. מכאן לבדו לא נובע אם היא נמצאת גם ב-NP.

קידוד ענף מפורש יותר

נניח שלכל קונפיגורציה של NN יש לכל היותר bb ממשיכים חוקיים, כאשר bb תלוי רק בטבלת המעברים הקבועה. ממספרים אותם 0,…,b−10,\ldots,b-1 ומגדירים

r=⌈log⁡2b⌉.r=\lceil\log_2b\rceil.

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

בכיוון ההפוך, NTM המדמה מוודא אינה צריכה לכתוב ברצף את כל 2p(n)2^{p(n)} התעודות. היא מסתעפת פעם אחת לכל ביט ומייצרת עץ חישוב בעומק p(n)p(n). זמן אי־דטרמיניסטי מודד את אורך הענף הארוך ביותר, לא את מספר הקודקודים הכולל בעץ. כל ענף משקיע p(n)p(n) צעדים בניחוש ואז הרצה פולינומיאלית אחת של VV. זו הסיבה המדויקת לכך שמספר מעריכי של מועמדים תואם זמן אי־דטרמיניסטי פולינומיאלי.

תעודה כרצף קונפיגורציות

אם מעדיפים תעודה שקל יותר לבדוק מקומית, אפשר לרשום C0,C1,…,CTC_0,C_1,\ldots,C_T. כל קונפיגורציה משתמשת ב-O(T)O(T) תאי סרט, ולכן אורך הרשימה O(T2)O(T^2). המוודא בודק ש-C0C_0 היא קונפיגורציית ההתחלה על xx, שכל Ci+1C_{i+1} מתקבלת מ-CiC_i במעבר חוקי אחד, וש-CTC_T מקבלת. בדיקת זוג סמוך פולינומיאלית, ויש מספר פולינומיאלי של זוגות. זהו גם הגשר הרעיוני לטבלת Cook–Levin.

8. דוגמאות נוספות לאי־סימטריה

ב-Hamiltonian Cycle, סדר מחזורי של הקודקודים הוא תעודת כן: בודקים שכל קודקוד מופיע פעם ושכל זוג עוקב, כולל האחרון והראשון, מחובר. לטענה שאין מעגל כזה אין תעודה דומה הנובעת מן ההגדרה; היא נמצאת ב-coNP מפני שמעגל אחד מפריך אותה.

ב-Subset Sum, וקטור ביטים בוחר מספרים וסכומם נבדק בינרית. לתשובת לא צריך לכאורה לשלול את כל תתי־הקבוצות. שוב, זו אינטואיציה לכמתים ולא הוכחת הפרדה.

לעומת זאת, בעיה ב-P מקבלת ראיות לשני הצדדים באופן טריוויאלי: המוודא יכול להתעלם מן התעודה ולהריץ את המכריע. לכן אין סתירה בכך ש-PRIMES ו-COMPOSITE נמצאות שתיהן ב-NP וב-coNP.

9. מה קורה אם שפה שלמה נמצאת ב-coNP?

תהי KK NP-שלמה ונניח K∈coNPK\in\mathrm{coNP}. לכל A∈NPA\in\mathrm{NP} קיימת ff כך ש-

x∈A  ⟺  f(x)∈K.x\in A\iff f(x)\in K.

אותה שקילות נותנת מיד

x∈A‾  ⟺  f(x)∈K‾.x\in\overline A\iff f(x)\in\overline K.

מן ההנחה נובע K‾∈NP\overline K\in\mathrm{NP}. מחשבים f(x)f(x) ומפעילים מוודא NP של K‾\overline K; לכן A‾∈NP\overline A\in\mathrm{NP}, כלומר A∈coNPA\in\mathrm{coNP}. קיבלנו NP⊆coNP\mathrm{NP}\subseteq\mathrm{coNP}. לקיחת משלימים נותנת את ההכלה ההפוכה והשוויון.

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

שימו לב להבדל בין NP-קשה ל-NP-שלמה. אם KK רק NP-קשה ונמצאת ב-coNP, אותו טיעון עדיין מעביר שייכות לכל שפת NP. אבל כדי לכנות את KK NP-שלמה נדרשת בנוסף הוכחה נפרדת ש-K∈NPK\in\mathrm{NP}.

10. מוודא אינו חייב למצוא את התעודה

הגדרת NP מפרידה בכוונה בין קיום לבין מציאה. המוודא מקבל את ww כחלק מן הקלט שלו ואינו נדרש לייצר אותו. לדוגמה, מוודא SAT אינו מחפש השמה: הוא קורא את הביט של כל משתנה ובודק את הפסוקיות. מוודא Hamiltonian Cycle אינו בונה מסלול: הוא בודק את סדר הקודקודים שנמסר לו.

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

גם ייחוד התעודה אינו נדרש. לנוסחת SAT עשויות להיות השמות מספקות רבות, ולגרף עשויים להיות מעגלים המילטוניים רבים. ה-NTM צריכה רק ענף מקבל אחד; כל שאר הענפים רשאים לדחות.

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

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

  1. לפרש NP כ״זמן מעריכי״.
  2. להחליף קבלה ודחייה ב-NTM כדי לקבל משלים.
  3. למדוד זמן בערך המספרי ולא באורך הקידוד.
  4. לאפשר תעודה בלתי־חסומה.
  5. להסיק ממועמד כושל שאין מועמד מצליח.
  6. לצייר הפרדות מחלקות כאילו הן ידועות.

תרגילים

תרגיל 1 — P⊆NP∩coNP\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}

הוכיחו P⊆NP\mathrm P\subseteq\mathrm{NP} ו-P⊆coNP\mathrm P\subseteq\mathrm{coNP}. ציינו מה לא הוכחתם על NP∩coNP\mathrm{NP}\cap\mathrm{coNP}.

פתרון

מכונה דטרמיניסטית פולינומיאלית היא NTM בעלת ענף יחיד, לכן P⊆NP\mathrm P\subseteq\mathrm{NP}. אם L∈PL\in\mathrm P, מחליפים קבלה ודחייה במכריע הכולל ומקבלים מכריע ל-L‾\overline L באותו זמן, לכן L‾∈P⊆NP\overline L\in\mathrm P\subseteq\mathrm{NP} ו-L∈coNPL\in\mathrm{coNP}.

לא הוכח: NP∩coNP=P\mathrm{NP}\cap\mathrm{coNP}=\mathrm P (פתוח). ידועה רק ההכלה P⊆NP∩coNP\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}.

תרגיל 2 — תעודת מסלול המילטוני

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

פתרון

תעודה: סדרת ∣V∣|V| מזהים. בודקים שהיא תמורה של VV, שכל זוג עוקב הוא קשת, ושקשת סגירה קיימת (למעגל) או שמדובר במסלול לפי הגדרת השפה. אורך O(∣V∣log⁡∣V∣)O(|V|\log|V|), זמן פולינומיאלי. שלמות/נאותות לפי הגדרת המסלול/המעגל.

תרגיל 3 — תעודת coNP לאי־טאוטולוגיה

תהי LL שפת הנוסחאות שאינן טאוטולוגיות. הוכיחו L∈NPL\in\mathrm{NP} ולכן שפת הטאוטולוגיות ב-coNP\mathrm{coNP}.

פתרון

תעודה ל-LL: השמה המפריכה את הנוסחה. אימות: הצבה וחישוב הערך בזמן פולינומיאלי. לכן L∈NPL\in\mathrm{NP}, ומשלימה (טאוטולוגיות) ב-coNP\mathrm{coNP}.

תרגיל 4 — חסם על ∣w∣|w|

הוכיחו מדוע בהגדרת מוודא חייבים לחסום ∣w∣≤q(∣x∣)|w|\le q(|x|). מה נשבר בלי החסם?

פתרון

ה-NTM המקבילה מנחשת את ww; בלי חסם הניחוש אינו פולינומיאלי ב-∣x∣|x|. גם קריאת ww לבדה עלולה להיות לא פולינומיאלית באורך הקלט. החסם מבטיח NP=⋃kNTIME(nk)\mathrm{NP}=\bigcup_k\mathrm{NTIME}(n^k).

תרגיל 5 — NP-שלמה ב-P\mathrm P

הוכיחו: אם קיימת שפה NP-שלמה ב-P\mathrm P, אז P=NP\mathrm P=\mathrm{NP}.

פתרון

תהי AA NP-שלמה ו-A∈PA\in\mathrm P. לכל L∈NPL\in\mathrm{NP} קיימת רדוקציה פולינומיאלית L≤pAL\le_p A. הרכבה עם מכריע פולינומיאלי ל-AA נותנת מכריע פולינומיאלי ל-LL. לכן NP⊆P\mathrm{NP}\subseteq\mathrm P, ומכאן שוויון.

סיכום

NP\mathrm{NP} הוא קיום תעודה קצרה הניתנת לאימות יעיל; coNP\mathrm{coNP} הוא ראיית־לא. ההכלות עם P\mathrm P ידועות; השוויונות המעניינים פתוחים.

תרגול מודרך

משימה 1 — מוודא אינו מוצא תעודה

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

פתרון

המוודא מקבל (x,w)(x,w) ובודק. מציאת ww היא בעיית חיפוש שעשויה להיות קשה גם כשהאימות קל. שייכות ל-NP\mathrm{NP} אינה מספקת אלגוריתם למציאת העד.

משימה 2 — סגירות למשלים

הוכיחו ש-P\mathrm P סגורה למשלים. הסבירו מדוע אותה הוכחה נכשלת ל-NP\mathrm{NP} בלי הנחות נוספות.

פתרון

ב-P\mathrm P מחליפים קבלה/דחייה במכריע דטרמיניסטי. ב-NP\mathrm{NP} החלפה בעץ משנה ∃\exists ל-״∃\exists ענף דוחה״ ולא ל-∀\forall. לכן סגירות NP\mathrm{NP} למשלים שקולה ל-NP=coNP\mathrm{NP}=\mathrm{coNP}, שאינה ידועה.

משימה 3 — NP∩coNP\mathrm{NP}\cap\mathrm{coNP}

תנו דוגמה לבעיה טבעית החשודה כנמצאת ב-NP∩coNP\mathrm{NP}\cap\mathrm{coNP} אך לא ידוע אם ב-P\mathrm P, והסבירו מה כן ידוע על החיתוך.

פתרון

דוגמה קלאסית: מספרים ראשוניים (PRIMES) — ב-P\mathrm P כיום, אך היסטורית דוגמה לחיתוך. באופן כללי ידוע P⊆NP∩coNP\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}; לא ידוע שוויון. שפות שלמות ל-NP\mathrm{NP} אינן יכולות להיות ב-coNP\mathrm{coNP} אלא אם NP=coNP\mathrm{NP}=\mathrm{coNP}.

מקורות

עדויות הקורס

  • תמלילי סמסטר א׳ הנוכחי 7–8: בדיקת תעודות, חישוב אי־דטרמיניסטי ואפיון NP באמצעות מוודא ו-NTM. לא נטען כאן למיקום מדויק יותר בתמליל.
  • הסיכום הממוזג, עמ׳ 39–42: הגדרות הליבה של NP, תעודות פולינומיאליות ונקודת המבט של מוודא ומכונה אי־דטרמיניסטית.
  • הסיכום הממוזג, עמ׳ 81–85: משלים, coNP, אי־סימטריה של ראיות והדיון ב-NP מול coNP. טווחי העמודים משמשים כעדות קורס; לא הועתק ניסוח מן הסיכום הסרוק.

אימות מספרי לימוד

  • Sipser, Introduction to the Theory of Computation, מהדורה שלישית, §7.3, עמ׳ 293–299.
  • Arora–Barak, Computational Complexity: A Modern Approach (טיוטה), §2.1–2.2, עמ׳ 38–45 במספור הטיוטה.
  • Papadimitriou, Computational Complexity, פרק 9, עמ׳ 181–187. הספרים מאמתים את המשפטים הסטנדרטיים; סדר ההצגה והדוגמאות מבוססים על הקורס.

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

3 עמודים

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