שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה - ספיקות

**רקע.** נוסחת $k$-CNF היא $\varphi=\varphi_1\wedge\varphi_2\wedge\cdots\wedge\varphi_m$, כשכל **פסוקית** היא $\varphi_i=(z_{i,1}\vee z_{i,2}\vee\cdots\vee z_{i,k})$ וכל $z_{i,j}$ הוא ליטרל מבין $x_1,\dots,x_n,\neg x_1,\dots,\neg x_n$. **השמה** מתאימה לכל משתנה ערך $T$/$F$; היא **מספקת** את $\varphi$ אם כל פסוקית מסופקת (לפחות ליטרל אחד בה אמת). הנוסחה **ספיקה** אם קיימת השמה מספקת. הציגו אלגוריתם **יעיל** שבהינתן נוסחה $\varphi$ בצורת **2-CNF** מוצא לה השמה מספקת, ואם אין כזו — מדווח שהנוסחה אינה ספיקה. **הדרכה:** היעזרו בגרף מכוון $G$ המותאם לנוסחה $\varphi$.

רמז: כל פסוקית $(a\vee b)$ שקולה לשתי גרירות: $\neg a\Rightarrow b$ ו-$\neg b\Rightarrow a$. בנו גרף גרירה, חשבו רכיבי קשירות חזקה, ובדקו האם קיים משתנה $x_i$ שעבורו $x_i$ ו-$\neg x_i$ באותו רכיב.

פתרון: נפתור באמצעות **גרף הגרירה (implication graph)** ו**רכיבי קשירות חזקה (SCC)**. **בניית גרף הגרירה $G$.** לכל משתנה $x_i$ ניצור שני קדקודים, $x_i$ ו-$\neg x_i$ (סה"כ $2n$ קדקודים). כל פסוקית $(a\vee b)$ שקולה לשתי גרירות: $\neg a\Rightarrow b$ וגם $\neg b\Rightarrow a$ (אם ליטרל אחד שקרי — השני חייב להיות אמת). נוסיף לכל פסוקית את שתי הצלעות המכוונות המתאימות (פסוקית יחידה $(a)$ מטופלת כ-$\neg a\Rightarrow a$). מספר הצלעות $O(m)$. **מבחן ספיקות.** נחשב את רכיבי הקשירות החזקה של $G$ (Tarjan/Kosaraju, $O(n+m)$). הנוסחה **ספיקה אם ורק אם לאף משתנה $x_i$ אין את $x_i$ ואת $\neg x_i$ באותו רכיב קשירות חזקה.** הנימוק: אם $x_i$ ו-$\neg x_i$ באותו SCC אז $x_i\Rightarrow\neg x_i$ וגם $\neg x_i\Rightarrow x_i$, כלומר שני הערכים מובילים לסתירה — אין השמה עקבית. **בניית השמה מספקת** (במקרה הספיק): גרף הרכיבים המכווץ הוא DAG; נמצא לו **מיון טופולוגי**. לכל משתנה נציב: $$x_i = T \iff \text{comp}(x_i) \text{ מופיע אחרי } \text{comp}(\neg x_i) \text{ במיון הטופולוגי},$$ ואחרת $x_i=F$. השמה זו עקבית עם כל הגרירות (לעולם לא $T\Rightarrow F$), ולכן מספקת את $\varphi$. **דיווח על אי-ספיקות:** אם קיים $x_i$ עם $x_i,\neg x_i$ באותו SCC — דווח ש-$\varphi$ אינה ספיקה. **זמן ריצה.** בנייה $O(n+m)$, SCC $O(n+m)$, מיון טופולוגי ובניית השמה $O(n+m)$ — סה"כ **$O(n+m)$**, ליניארי. $\blacksquare$