דרישות קדם מתמטיות ואלגוריתמיות

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

מטרות

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

אינטואיציה

תורת הסיבוכיות חוקרת כיצד המשאבים הדרושים גדלים עם אורך הקלט. היא מתעלמת מהבדלים הנדסיים של גורם קבוע, אך לא מהקידוד: לייצוג בינרי של מספר $n$ יש אורך $\Theta(\log n)$, ולא $n$.

משתנה הגודל הוא בדרך כלל $n=|x|$, אורך הייצוג. למספר $N$ יש ייצוג בינרי באורך $\lfloor\log_2N\rfloor+1$, אך ייצוג אונרי באורך $N$. לכן אלגוריתם המבצע $O(N)$ איטרציות הוא ליניארי בקלט אונרי ומעריכי באורך הקלט הבינרי. הקידוד הוא חלק מן הבעיה.

בעיית הכרעה מיוצגת כשפה $L\subseteq\Sigma^*$. מכריע $M$ חייב לעצור על כל קלט, לקבל בדיוק את המילים ב-$L$ ולדחות את כל האחרות. אלגוריתם הוא השיטה המופשטת; מודל המכונה קובע מה נחשב צעד ומהם המשאבים הנמדדים.

קבוצות, מחרוזות וגרפים

$\Sigma^*$ היא קבוצת כל המחרוזות הסופיות מעל האלפבית $\Sigma$, כולל $\varepsilon$. קידוד זוג $\langle x,y\rangle$ חייב להיות חד־משמעי וניתן לפענוח יעיל; השרשור $xy$ לבדו עלול לאבד את הגבול. גרף יכול להיכתב כמטריצת שכנויות בגודל $\Theta(|V|^2)$ או כרשימת צלעות בגודל $O((|V|+|E|)\log|V|)$. מעבר בין קידודים דורש הוכחה שאורכיהם קשורים פולינומיאלית.

דוגמת קידוד. תוכנית המונה מ-$0$ עד $N$ מבצעת $\Theta(N)$ צעדים. על הקלט $1^N$ זה זמן ליניארי. על ייצוג בינרי באורך $n=\Theta(\log N)$, מספר הצעדים הוא $2^{\Theta(n)}$. אותה תוכנית מקבלת סיווג שונה משום שאורך הקלט השתנה.

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

לפונקציות אי־שליליות לבסוף, $f(n)=O(g(n))$ אם קיימים $c,n_0>0$ כך שלכל $n\ge n_0$ מתקיים $f(n)\le c g(n)$. מגדירים $\Omega$ בהיפוך האי־שוויון ו-$\Theta=O\cap\Omega$. שפה היא קבוצה $L\subseteq\{0,1\}^*$.

באופן מלא,

$O$ הוא חסם עליון לבסוף, לא שוויון. $o$ מתאר שליטה ממש: $n^2=o(n^3)$, אך $3n^2\not=o(n^2)$. בין עובדות הגדילה השימושיות:

שינוי בסיס קבוע של לוגריתם משנה גורם קבוע בלבד; לעומת זאת $2^{cn}$ ו-$2^n$ אינם בהכרח במרחק גורם קבוע.

טענה. אם אלגוריתם מבצע לכל היותר $n^3+7n$ צעדים על כל קלט באורך $n$, אז זמן הריצה שלו הוא $O(n^3)$.

מהלך ההוכחה

יהי $T(n)$ מספר הצעדים במקרה הגרוע על קלטים באורך $n$. נתון $T(n)\le n^3+7n$ לכל $n\ge1$. יש להציג קבועים $c,n_0>0$ כך שלכל $n\ge n_0$ מתקיים $T(n)\le cn^3$.

עבור $n\ge1$ מתקיים $7n\le7n^3$, ולכן

הבחירה $c=8$ ו-$n_0=1$ מקיימת את הגדרת $O$ במפורש. אין די באמירה שהאיבר המעוקב ״שולט״: ההוכחה חייבת לספק עדים מכומתים.

טענה. $4n^2+3n+9=\Theta(n^2)$.

חסם עליון. עבור $n\ge1$: $3n\le3n^2$ ו-$9\le9n^2$, ולכן $4n^2+3n+9\le16n^2$. בחרו $c=16,n_0=1$.

חסם תחתון. לכל $n$ מתקיים $4n^2+3n+9\ge4n^2$. בחרו $c'=4,n_0'=1$. שני הכיוונים נדרשים; כל כיוון מספק קבועים משלו.

בהמחשה כדאי להשוות $\log n,n,n\log n,n^2,2^n$ גם בציר רגיל וגם בציר לוגריתמי. חציות עבור $n$ קטן אינן משנות את הסדר האסימפטוטי.

שיטות הוכחה

הוכחה ישירה ובנייה

להוכחת $A\subseteq B$ לוקחים $x\in A$ שרירותי ומסיקים $x\in B$. להוכחת שייכות למחלקת סיבוכיות בונים מכונה אחת, מוכיחים נכונות, עצירה וחסם משאבים. קיום אלגוריתם איטי אינו שולל קיום אלגוריתם מהיר.

קונטרה־פוזיטיב וסתירה

$P\Rightarrow Q$ שקול ל-$\neg Q\Rightarrow\neg P$, אך לא להיפוך $Q\Rightarrow P$. בהוכחה בדרך השלילה יש לנסח במדויק את השלילה. למשל, שלילת $\forall x\,\exists y\,R(x,y)$ היא $\exists x\,\forall y\,\neg R(x,y)$.

אינדוקציה

מוכיחים בסיס ומעבר $P(n)\Rightarrow P(n+1)$. בסימולציות מכונות האינווריאנט הטיפוסי הוא: לאחר $i$ צעדי סימולציה, הקידוד מייצג בדיוק את הקונפיגורציה לאחר $i$ צעדים של המכונה המדומה. הבסיס בודק את הקלט, והמעבר בודק מעבר יחיד.

ספירה ושובך היונים

יש $2^n$ מחרוזות בינריות באורך $n$, אך $2^{2^n}$ פונקציות בוליאניות על $n$ ביטים. פער זה מוכיח שקיימות פונקציות שאינן ניתנות לייצוג קטן מסוגים מסוימים, אף שאינו בהכרח מזהה פונקציה מפורשת.

לכסון

מונה מכונות $M_1,M_2,\ldots$ ובונים אובייקט החולק על $M_i$ בקלט הייעודי ה-$i$. אין די בסיסמה ״נהפוך את התשובה״: יש להבטיח שהסימולטור עוצר ונכנס בתקציב. משום כך משפטי היררכיה כוללים תנאי בנייה ופער.

הסתברות

במרחב סופי $\Omega$, אירוע הוא תת־קבוצה ו

כאשר $\Pr[B]>0$. אי־תלות פירושה $\Pr[A\cap B]=\Pr[A]\Pr[B]$. אי־תלות בזוגות אינה מבטיחה אי־תלות משותפת.

חסם האיחוד אינו דורש אי־תלות:

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

תקפה גם למשתנים תלויים. עבור אינדיקטור $I_A$, מתקיים $\mathbb E[I_A]=\Pr[A]$.

הגברה. אם ריצה עצמאית מצליחה בהסתברות $2/3$ ואין קבלה שגויה, אז $k$ ריצות וקבלה אם אחת הצליחה נכשלות בהסתברות לכל היותר $(1/3)^k$. בשגיאה דו־צדדית והצבעת רוב דרוש חסם ריכוז; הנוסחה הזו אינה מספיקה. ״בהסתברות גבוהה״ פירושו בדרך כלל לפחות $1-1/n^c$ עבור $c>0$ קבוע, ולא רק מעל חצי.

קריאת טענות פורמליות

סדר הכמתים קובע תלות. ב-$\forall M\,\exists c_M\,\forall x$, הקבוע תלוי במכונה אך לא בקלט. טענה עם $\exists c\,\forall M\,\forall x$ חזקה בהרבה. בכל הוכחת חברות במחלקה מפרידים:

1. סמנטיקה — המכונה מכריעה בדיוק את השפה.
2. עצירה — כל החישובים הנדרשים עוצרים.
3. משאבים — החסם מתקיים לכל קלט באורך הנתון.

דוגמה פתורה

גרף עם $N$ קודקודים דורש $\Theta(N^2)$ ביטים כמטריצת שכנויות, אך $\Theta((N+M)\log N)$ ביטים כרשימת צלעות. לכן יש לבדוק שפולינומיאליות נשמרת ביחס לקידוד הרלוונטי.

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

• להתייחס ל-$O(g)$ כשוויון.
• למדוד קלט מספרי לפי ערכו ולא לפי מספר הביטים.
• לפרש ״בהסתברות גבוהה״ כ״יותר מחצי״ בלבד.
• להוכיח דוגמאות במקום את כל המקרים המכומתים.
• להכפיל הסתברויות ללא אי־תלות.
• להסתיר קבוע התלוי בקלט.
• להוכיח נכונות רק למופעים חיוביים.

הצעת המחשה

להציג את $\log n,n,n\log n,n^2,2^n$ בציר אנכי לוגריתמי ולסמן מאיזה תחום סדר הגדילה מתבהר.

תרגילים

תרגיל 1 — הוכחת $\Theta$

הוכיחו מההגדרה כי $2n^3+100n^2=\Theta(n^3)$. ציינו במפורש את הקבועים ואת $n_0$ בכל כיוון.

תרגיל 2 — הפרכת $O$

הוכיחו כי הטענה $2^n=O(n^{100})$ שגויה. כתבו את השלילה של הגדרת $O$ והשלימו אותה.

תרגיל 3 — קידוד אונרי מול בינרי

תהי $A$ השפה של קלטים אונריים $1^N$, ותהי $B$ השפה של ייצוגים בינריים של אותם מספרים. אלגוריתם מונה מ-$0$ עד $N$ ב-$\Theta(N)$ צעדים. הוכיחו כי האלגוריתם רץ בזמן ליניארי באורך הקלט על קלט מ-$A$, אך מעריכי באורך הקלט על קלט מ-$B$. הסבירו מדוע אין סתירה.

תרגיל 4 — חסם איחוד בלי אי־תלות

נבחרים $k$ ערכים; לכל $i$, ההסתברות שהערך ה-$i$ רע היא לכל היותר $1/n^2$. הוכיחו כי ההסתברות שלפחות ערך אחד רע היא לכל היותר $k/n^2$, בלי להניח אי־תלות. הסיקו את המקרה $k=n$. הסבירו מדוע אסור להכפיל את הסתברויות ההצלחה בלי הנחה נוספת.

תרגיל 5 — תוחלת עם תלות

יהי $G=(V,E)$ גרף. לכל קודקוד $v$ נסמן ב-$I_v$ אינדיקטור לכך ש-$v$ נבחר, ונניח $\Pr[I_v=1]=p$ לכל $v$. יהי $X=\sum_{v\in V}I_v$. הוכיחו כי $\mathbb E[X]=|V|p$ גם אם מנגנון הבחירה יוצר תלות בין הקודקודים.

סיכום

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

תרגול מודרך

משימה 1 — כמתים ותלות קבועים

נסחו במדויק את שני המשפטים הבאים והשוו את חוזקם:

1. לכל מכונה $M$ קיים קבוע $c_M$ כך שלכל קלט $x$ מתקיים $T_M(x)\le 2^{c_M\,|x|}$.
2. קיים קבוע $c$ אחד כך שלכל מכונה $M$ ולכל קלט $x$ מתקיים $T_M(x)\le 2^{c\,|x|}$.

באיזו מהן מותר שהקבוע תלוי ב-$M$? האם מותר לבחור את הקבוע אחרי שרואים את $x$?

משימה 2 — שלושת חלקי הוכחת שייכות

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

משימה 3 — מקרה מסכם: זמן, קידוד והסתברות

אלגוריתם מקבל מספר בינרי $N$, יוצר $N$ ניסויים, ובכל ניסוי אירוע רע בהסתברות לכל היותר $1/N^3$ (ללא הנחת אי־תלות בין הניסויים).

1. הוכיחו כי האלגוריתם אינו פולינומיאלי באורך הקלט $n=|N|$.
2. הוכיחו חסם על ההסתברות לאירוע רע כלשהו.
3. הסבירו מתי הסתברות כישלון קטנה מ-$1$ מוכיחה קיום בחירה טובה, ומתי אין זה מספיק לאלגוריתם יעיל.
4. הבחינו בין זמן תוחלת לבין זמן מקרה גרוע.

מקורות

• ראיית סיכום סטודנטים: הסיכום הממוזג, עמ' 1, 98 ו-141; משמש להתאמת דגשים בלבד ולא כאסמכתה סופית.
• ראיית קורס: תמלילי סמסטר א' 2026, שיעורים 1-2, למסגור יסודות הקורס; אין כאן טענה למיקום שורות מדויק.
• אימות: Sipser, מהדורה 3, עמ' 3-24.
• אימות: Arora-Barak, טיוטה, עמ' 9-14 ונספח A.
• אימות: Papadimitriou, עמ' 1-18 ופרק ההסתברות.