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

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

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

פתרון: **נוסחה נגדית.** $$\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$