שיבוץ נגישות מכוונת ב־NL

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

שאלה

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

דרישות קדם

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

רמז 1

אם קיים מסלול, קיים מסלול פשוט באורך לכל היותר $n-1$.

רמז 2

שמרו רק קודקוד נוכחי.

רמז 3

נחשו קודקוד הבא ובדקו קשת בסריקת הקלט.

פתרון מלא

נשמור קודקוד נוכחי $v$, מאותחל ל-$s$, ומונה $i=0$. אם $v=t$ נקבל. כל עוד $i<n-1$, ננחש $u\in\{1,\ldots,n\}$, נסרוק את הקלט לקריאה בלבד ונבדוק אם $(v,u)\in E$. אם לא, הענף דוחה; אחרת נעדכן $v:=u$, נגדיל מונה ונבדוק שוב אם הגענו ל-$t$. בתום התקציב דוחים.

כל קודקוד ומונה דורשים $O(\log n)$ ביטים. גם מיקומי ראשי הקלט ודגלים קבועים דורשים מקום לוגריתמי. במטריצת שכנויות מחשבים אינדקס בעזרת מונים; ברשימות שכנות סורקים תוך שמירת $v,u$. סריקות חוזרות עולות זמן אך לא מקום.

אם יש מסלול, מחיקת מעגלים נותנת מסלול פשוט באורך לכל היותר $n-1$, וענף אחד ינחש אותו. אם אין מסלול, כל רצף קשתות מאומת הוא הליכה מ-$s$ ולעולם לא יגיע ל-$t$. כל ענף עוצר בגלל המונה, ולכן זה מכריע ו-$\mathrm{STCON}\in\mathrm{NL}$.

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

נקודות בדיקה

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

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

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

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

• Merged summary, pp. 114-117
• Sipser 3e, sec. 8.4
• Arora-Barak draft, sec. 4.3
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

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

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