ii. קלט: גרף מכוון G = (V,E) ושני קודקודים s,t V. שאלה: האם קיים בגרף G מסלול מ-s ל-t ש-3 מחלק את מספר קשתותיו…

ii. קלט: גרף מכוון G = (V,E) ושני קודקודים $s,t \in V$. שאלה: האם קיים בגרף G מסלול מ-s ל-t ש-3 מחלק את מספר קשתותיו? נסמן את השפה ב-A. נוכיח כי $A\in NL$. נתבונן באלגוריתם הבא: קלט $G=(V,E) , s,t\in V$ : אתחול- u=s . [הערה] * שינויים מהאלגוריתם של st-CONN 1. לכל j=1,2,...,3|V| 1.1 נבחר באופן אי-דטרמיניסטי שכן v של u . 1.2 אם v=t ואם 3|j קבל. 1.3 u=v 2. דחה. ניתוח סיבוכיות מקום: יהי G=(V,E) גרף מכוון ויהיו $s,t\in V$ . בריצת האלגוריתם על G,s,t האלגוריתם זוכר את המונה j ואת הקודקודים u,v בכל רגע נתון$. 1 \le j \le 3|V|$ ו$- u,v\in V$ סך הכל- O(log|<G,s,t>|) = O(log|V|) מקום. ניתוח נכונות: נראה כי האלגוריתם מכריע את A . יהי G=(V,E) גרף מכוון ויהיו $s,t\in V$ . נניח $- (G,s,t)\in A$ : אז קיים מסלול מ-s ל-t שאורכו מתחלק ב-3. לכן קיים מסלול מ-s ל-t שאורכו מתחלק ב-3 באורך הקצר ביותר. נסמן P . יהי $v\in V$ . נניח בשלילה ש-v מופיע ב-P 4 פעמים. נסמן P=s=v_1-v_2-...-v_ℓ=t אז קיימים $1\le i<j<k<m\le ℓ$ כך ש$- v_i=v_j=v_k=v_m$ . מקרה 1: 3|j-i או 3|k-j או 3|m-k - ללא הגבלת הכלליות, 3|j-i. נסמן ב-P' את המסלול המתקבל מ-P ע"י מחיקת המקטע בין $v_i$ ל$-v_j . P$' מסלול מ-s ל-t שאורכו מתחלק ב-3, וקצר מאורכו של P בסתירה. מקרה 2: j-i , k-j , m-k מתחלקים ב-3 עם שארית 1 - מחיקה של שלושת המקטעים ב-P בין $v_i$ ל$-v_j$ , בין $v_j$ ל$-v_k$ ובין $v_k$ ל$-v_m$ מניבה מסלול P' מ-s ל-t שאורכו מתחלק ב-3 , וקצר מאורכו של P בסתירה. מקרה 3: j-i , k-j , m-k מתחלקים ב-3 עם שארית 2 - בדומה. מקרה 4: מבין המקטעים j-i , k-j , m-k יש אותם המתחלק ב-3 עם שארית ואותם המתחלק ב-3 עם שארית [לא ברור]: ניתן למחוק את 2 המקטעים המתאימים ולקבל מסלול P' בדומה למקרים הקודמים. לכן לכל $v\in V , v$ מופיע ב-P לכל היותר 3 פעמים. לכן $|P|\le3|V|$ . לכן קיימת ריצה של האלגוריתם שבה הוא מנחש את P באופן אי-דטרמיניסטי.