מחלקות סיבוכיות דטרמיניסטיות

DTIME, DSPACE, P ורעיונות היררכיה בחישוב דטרמיניסטי.

מטרות

• להגדיר $\mathrm{DTIME}$, $\mathrm{DSPACE}$ ו-$\mathrm P$.
• להוכיח הכלות בסיסיות מתוך גבולות משאבים.
• להבין את תפקיד פונקציות הבנייה במשפטי היררכיה.

אינטואיציה

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

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

$\mathrm{DTIME}(t(n))$ ו-$\mathrm{DSPACE}(s(n))$ מכילות שפות שמכונות דטרמיניסטיות מכריעות בגבולות אלה. מגדירים

נגדיר גם

בחלק מהספרים $\mathrm{EXP}$ נקראת $\mathrm{EXPTIME}$. האיחוד בולע בחירה של מעריך פולינומיאלי קבוע, אך לא מעבר מפולינום למעריך. כל ההגדרות הן חסמי מקרה גרוע של מכריעים עוצרים.

יש לקרוא חץ כהכלה מוכחת ולא כשוויון. השרשרת הבסיסית היא

טענה. $\mathrm P\subseteq\mathrm{PSPACE}$.

מהלך ההוכחה

נקבע $k\ge1$ ונראה $\mathrm{DTIME}(n^k)\subseteq\mathrm{DSPACE}(n^k)$. תהי $L\in\mathrm{DTIME}(n^k)$, ויהי $M$ מכריע דטרמיניסטי העוצר תוך לכל היותר $n^k$ צעדים על כל קלט באורך $n$.

בכל צעד ראש עבודה זז לכל היותר תא אחד. לכן בריצה של לכל היותר $n^k$ צעדים מבקרים ב־לכל היותר $n^k$ תאי עבודה (בתוספת מספר קבוע של תאים לתחזוקה, הנבלע ב-$O$). מכאן $L\in\mathrm{DSPACE}(n^k)$.

מכיוון שזה נכון לכל $k$,

האיחוד סוגר את הטענה: אין צורך במעריך יחיד לכל $\mathrm P$.

מה אין כאן. ההוכחה אינה מראה $\mathrm P=\mathrm{PSPACE}$, ואינה מראה הפרדה. היא גם אינה קובעת חסם מקום הדוק לבעיה ספציפית מעבר למה שהסימולציה נותנת.

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

ספירת קונפיגורציות והכלות

למכונה קבועה המשתמשת ב-$s(n)\ge\log n$ מקום, קונפיגורציה כוללת מצב קבוע, $O(s(n))$ סימני עבודה, מיקומי ראשי עבודה ומיקום ראש קלט מתוך $n+1$ אפשרויות. לכן מספר הקונפיגורציות לכל היותר

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

טענה. $\mathrm{PSPACE}\subseteq\mathrm{EXP}$.

הוכחה. תהי $L\in\mathrm{PSPACE}$. אז קיים $k$ כך ש-$L\in\mathrm{DSPACE}(n^k)$. מההכלה לעיל,

קיים $c$ כך שהזמן $\le 2^{c n^k}$. עבור $k'=k+1$ (או מעריך גדול מספיק) מתקיים $c n^k\le n^{k'}$ לכל $n$ גדול, ולכן $L\in\mathrm{DTIME}(2^{n^{k'}})\subseteq\mathrm{EXP}$.

מכיוון שזמן חוסם מקום, גם $\mathrm{EXP}\subseteq\mathrm{EXPSPACE}$. יחד עם $\mathrm P\subseteq\mathrm{PSPACE}$ מתקבלת השרשרת

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

אך אינם פותרים את $\mathrm P$ מול $\mathrm{PSPACE}$.

פונקציות בנייה

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

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

היררכיית הזמן הדטרמיניסטית

בניסוח סטנדרטי, אם $t_1,t_2$ בנות־בנייה ו

אז

גורם הלוגריתם המדויק תלוי במודל הסימולציה.

מהלך ההוכחה

1. מונים מכונות דטרמיניסטיות מקודדות $M_1,M_2,\ldots$ ומאפשרים לתיאורים מרופדים להופיע באורכים גדולים כרצוננו.
2. מכריע אלכסוני $D$ מפרש חלק מהקלט $x$ כתיאור מכונה; תיאור פסול מקבל תשובה קבועה.
3. בעזרת בניית $t_2$ מפעילים שעון של $t_2(n)$ צעדים.
4. מדמים אוניברסלית את $M$ על אותו $x$ די זמן כדי לכסות חישוב $t_1(n)$ ואת תקורת הפענוח.
5. אם הסימולציה מקבלת בזמן, $D$ דוחה; אחרת $D$ מקבל.
6. תנאי הפער מבטיח שכל העבודה נכנסת ב-$O(t_2(n))$.
7. אילו מכונת $t_1$ כלשהי הכריעה את $L(D)$, נבחר קלט מרופד מספיק המקודד אותה. $D$ היה מחזיר את היפך תשובתה על אותו קלט — סתירה.

לא הופכים תשובה אחרי סימולציה בלתי־חסומה. פסק הזמן והפער הם שהופכים את $D$ למכריע במחלקה הגדולה.

היררכיית המקום הדטרמיניסטית

אם $s_1,s_2$ בנות־בנייה, לפחות לוגריתמיות, ו-$s_1=o(s_2)$, אז

גם כאן מונים מכונות ומדמים תיאור הנמצא בקלט בתוך תחום של $O(s_2(n))$ תאים. ניסיון לחצות את הגבול נקטע. אולם מכונה יכולה להיכנס ללולאה בלי לחרוג מן המקום, ולכן יש לספור עד $2^{O(s_2(n))}$ קונפיגורציות. המונה עצמו דורש רק $O(s_2(n))$ ביטים. אם המכונה נעצרת הופכים את תשובתה; אם נספרו יותר קונפיגורציות היא חזרה על אחת מהן. על תיאור מרופד של כל מכריע ב-$s_1$ מקום מתקבלת סתירת לכסון. מכאן בפרט $\mathrm{PSPACE}\subsetneq\mathrm{EXPSPACE}$.

ריפוד

עבור פונקציה עולה $p$, מגדירים

אם $N=p(n)$, אלגוריתם שזמנו $2^{O(n)}$ עשוי להיות פולינומיאלי באורך המרופד $N$ כאשר $p(n)=2^{\Theta(n)}$. זוהי שפה אחרת; הריפוד אינו מאיץ את הבעיה המקורית.

דוגמה. אם $L\in\mathrm{DTIME}(2^n)$, אז בקלט מהצורה $x\#1^{2^{|x|}-|x|}$ בודקים תחילה את המבנה ואז מריצים את המכריע המקורי. זמן $2^{|x|}$ הוא $O(N)$, ולכן השפה המרופדת ב-$\mathrm P$. בדיקת הריפוד והפענוח הם חלק מן האלגוריתם.

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

דוגמה פתורה

נגישות בגרף שייכת ל-$\mathrm P$: חיפוש לרוחב מסמן כל קודקוד וסורק את הצלעות בזמן פולינומיאלי. התור והסימונים משתמשים גם הם במקום פולינומיאלי.

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

• לפרש $\mathrm P$ כ״מהיר בפועל״.
• לטעון הפרדה בין שני חסמי זמן בלי לבדוק את תנאי משפט ההיררכיה.
• להתעלם מענפים שאינם עוצרים בעת הגדרת זמן ריצה.
• לפרש תרשים הכלות כהוכחת הפרדה.
• להשמיט בנייה או את פער ההיררכיה.
• לשכוח גילוי לולאות בסימולציית מקום.
• להחיל מסקנת ריפוד על השפה המקורית.

הצעת המחשה

לצייר אזורים מקוננים $\mathrm P\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXPTIME}$ ולהבדיל בין הכלות ידועות לשוויונות פתוחים.

תרגילים

תרגיל 1 — $\mathrm{DTIME}(n^k)\subseteq\mathrm{DSPACE}(n^k)$

הוכיחו במפורש כי לכל $k\ge1$ מתקיים $\mathrm{DTIME}(n^k)\subseteq\mathrm{DSPACE}(n^k)$, והסיקו $\mathrm P\subseteq\mathrm{PSPACE}$.

תרגיל 2 — מיקום שפה בשרשרת

לשפה $L$ יש מכריע המשתמש ב-$n^3$ תאי עבודה. הוכיחו $L\in\mathrm{PSPACE}$ ו-$L\in\mathrm{EXP}$. מה אי אפשר להסיק לגבי שייכות ל-$\mathrm P$?

תרגיל 3 — ביקורת היררכיית זמן

האם משפט היררכיית הזמן הסטנדרטי (עם תנאי $t_1\log t_1=o(t_2)$) מוכיח ישירות

הסבירו. הראו כיצד להפריד בין $n^2$ ל-$n^3$ תחת אותם תנאים.

תרגיל 4 — אלגברת ריפוד

נניח זמן מקורי $2^{n^2}$ ואורך מרופד $N=2^n$. הוכיחו כי הזמן כפונקציה של $N$ אינו פולינומיאלי. איזה ריפוד יהפוך את הסימולציה לליניארית ב-$N$?

תרגיל 5 — פולינום מול כמעט־פולינום

הוכיחו כי $2^{O(\log n)}$ הוא פולינומיאלי ב-$n$, אך $2^{O((\log n)^2)}$ אינו בהכרח פולינומיאלי.

סיכום

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

ביקורת משפט מודרכת

משימה 1 — האם ההוכחה תקפה?

סטודנט טוען: ״$\mathrm{DTIME}(n^2)\subsetneq\mathrm{DTIME}(n^2\log n)$ כי יש יותר זמן.״ פרטו אילו שלבים חסרים בתבנית הוכחת היררכיה, ומה ניתן להציל.

משימה 2 — ביקורת חסם מקום

מכריע משתמש ב-$n^2$ תאים. חסמו את מספר הקונפיגורציות ואת זמן העצירה. מתי מותר להחליף $2^{O(n^2)}$ ב-$2^{n^2}$?

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

1. הסבירו מדוע להוכחת $\mathrm P\subsetneq\mathrm{EXP}$ אין די בבחירת חזקה פולינומיאלית אחת.
2. בריפוד עם $N=n^4$: תרגמו זמנים $n^{12}$ ו-$2^n$ לאורך החדש.
3. מה מבדיל הפרדת מחלקות קיומית מסיווג בעיה טבעית ב-$\mathrm{EXP}\setminus\mathrm P$?

מקורות

• ראיית סיכום סטודנטים: הסיכום הממוזג, עמ' 6-24, 30, 36-39, 68-71, 107 ו-129-135; משמש להתאמת הקורס בלבד.
• ראיית קורס: תמלילי סמסטר א' 2026, שיעורים 2-4.
• אימות: Sipser, מהדורה 3, עמ' 275-279 ו-321-335.
• אימות: Arora-Barak, טיוטה, עמ' 65-88.
• אימות: Papadimitriou, עמ' 139-154.