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

נתונה נוסחת **3-CNF** $\varphi=\varphi_1\wedge\cdots\wedge\varphi_m$ (כל פסוקית שלושה ליטרלים). נתבונן ב**אלגוריתם החמדן** הבא למציאת השמה מספקת: האלגוריתם סורק את המשתנים $x_1,\dots,x_n$ בזה אחר זה, ולכל משתנה $x_i$ בוחר את הערך שממקסם את מספר הפסוקיות המסופקות **החדשות** (מבין אלו שטרם סופקו ע"י ההשמה החלקית שנקבעה עד כה). הציגו נוסחת 3-CNF שעליה האלגוריתם החמדן **נכשל**: הנוסחה ספיקה, אך האלגוריתם מפיק השמה שאינה מספקת.

רמז: בנו נוסחה שבה כל אחד מ-$x_1,x_2,x_3$ מופיע חיובי ביותר פסוקיות מאשר שלילי (כדי שהחמדן יבחר בכולם $T$), אך יש פסוקית אחת $(\neg x_1\vee\neg x_2\vee\neg x_3)$ הדורשת שלפחות אחד מהם יהיה $F$.

פתרון: **נוסחה נגדית.** $$\varphi=(x_1\vee x_2\vee x_3)\wedge(x_1\vee x_2\vee x_4)\wedge(x_2\vee x_3\vee x_4)\wedge(x_2\vee x_3\vee x_5)\wedge(x_3\vee x_4\vee x_5)\wedge(x_3\vee x_4\vee x_6)\wedge(\neg x_1\vee\neg x_2\vee\neg x_3).$$ **הנוסחה ספיקה.** ההשמה $x_3=F$ ו-$x_i=T$ לכל $i\neq 3$ מספקת את כולה: שש הפסוקיות הראשונות מסופקות ע"י ליטרל חיובי ($x_1,x_2$ או $x_4$), והפסוקית האחרונה מסופקת ע"י $\neg x_3$. **כישלון החמדן.** לכל משתנה בוחר החמדן את הערך המספק יותר פסוקיות חדשות: - $x_1$ מופיע חיובי ב-2 פסוקיות (הראשונות) ושלילי ב-1 (האחרונה) $\Rightarrow x_1=T$. - לאחר דילוג על הפסוקיות שסופקו, $x_2$ מופיע חיובי ב-2 מהנותרות ושלילי ב-1 $\Rightarrow x_2=T$. - באופן דומה $x_3=T$ (מופיע חיובי ביותר פסוקיות משלילי). מתקבל $x_1=x_2=x_3=T$, וכעת הפסוקית האחרונה $(\neg x_1\vee\neg x_2\vee\neg x_3)=(F\vee F\vee F)=F$ — **ההשמה אינה מספקת**, למרות שהנוסחה ספיקה. $\blacksquare$