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

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

נשתמש בהגדרות הבאות:

• נוסחה בוליאנית מצורת $CNF$ היא ספיקה במובן $NAE$ (Not All Equal) אם קיימת השמה שעבורה בכל הסגר יש ליטרל שערכו $True$ וליטרל שערכו $False$. עבור $k$ טבעי נגדיר $$k\text{-}NAE=\{\langle\varphi\rangle\mid\varphi\text{ נוסחת }k\text{-}CNF\text{ הספיקה במובן }NAE\}.$$
• נגדיר $$MAX\text{-}IS=\{\langle G,k\rangle\mid k\text{ הוא גודלה של הקבוצה הבלתי תלויה המקסימלית ב-}G\}.$$ כלומר, קיימת ב-$G$ קבוצה בלתי תלויה בגודל $k$, וכל קבוצה בלתי תלויה ב-$G$ היא בגודל לכל היותר $k$.

1. טענה: $3\text{-}SAT\le_p SAT$.
   אלגוריתם: לכל קלט $x$, החזר את $x$.

2. טענה: $3\text{-}NAE\le_p3\text{-}SAT$.
   אלגוריתם: לכל קלט $x$, החזר את $x$.

3. טענה: $3\text{-}SAT\le_p4\text{-}NAE$.
   אלגוריתם: בהינתן קידוד של נוסחה $\varphi$ מצורת $3$-$CNF$, נוסיף לכל אחד מהסגרי $\varphi$ משתנה חדש $x$ — אותו משתנה לכל ההסגרים — ונחזיר את הנוסחה המתקבלת בצירוף השמה הנותנת ל-$x$ את הערך $0$.

4. טענה: $3\text{-}SAT\le_p4\text{-}NAE$.
   אלגוריתם: בהינתן קידוד של נוסחה $\varphi$ מצורת $3$-$CNF$, נוסיף לכל אחד מהסגרי $\varphi$ משתנה חדש $x$ — אותו משתנה לכל ההסגרים — ונחזיר את הנוסחה המתקבלת.

5. טענה: $4\text{-}NAE\le_p3\text{-}NAE$.
   אלגוריתם: בהינתן נוסחה $\varphi$ מצורת $4$-$CNF$, נחליף כל הסגר של $\varphi$ הכולל ארבעה ליטרלים, כלומר הסגר מן הצורה

   $$(\ell_1\vee\ell_2\vee\ell_3\vee\ell_4),$$

   כאשר $\ell_i$ הוא ליטרל לכל $1\le i\le4$, בשני ההסגרים

   $$(\ell_1\vee\ell_2\vee x), \qquad (\ell_3\vee\ell_4\vee\bar x),$$

   עבור משתנה חדש $x$; לכל הסגר בנוסחה המקורית נוסף משתנה חדש שונה. נחזיר את הנוסחה המתקבלת.

6. טענה: $MAX\text{-}IS\le_p IS$.
   אלגוריתם: לכל קלט $x$, החזר את $x$.

7. טענה: $IS\le_p MAX\text{-}IS$.
   אלגוריתם: לכל קלט $x$, החזר את $x$.

8. טענה: $SAT\le_p IS$.
   אלגוריתם: בהינתן נוסחה $\varphi$ מצורת $CNF$ בעלת $m$ הסגרים, נחזיר את $(G,m)$, כאשר $G=(V,E)$ הוא גרף לא מכוון המוגדר כך:

   • קבוצת הקודקודים $V$: לכל הסגר של $\varphi$ ולכל השמה למשתני ההסגר המספקת את ההסגר, יוגדר קודקוד.
   • קבוצת הקשתות $E$: כל שני קודקודים המתאימים להשמות של אותו הסגר יחוברו בקשת. בנוסף יחוברו בקשת שני קודקודים המתאימים להשמות של הסגרים שונים אשר סותרות זו את זו, כלומר אחת מהן נותנת למשתנה מסוים ערך $1$ והאחרת נותנת לו ערך $0$.

   למשל, עבור הנוסחה

   $$(\bar x_1\vee x_3)\wedge(x_1\vee\bar x_2\vee x_3)$$

   יש שלוש השמות עבור המשתנים $x_1,x_3$ המספקות את ההסגר הראשון ושבע השמות עבור המשתנים $x_1,x_2,x_3$ המספקות את ההסגר השני; לכן בגרף יהיו עשרה קודקודים.

   ההשמה הנותנת $0$ ל-$x_1$ ו-$1$ ל-$x_3$ מספקת את ההסגר הראשון. ההשמה הנותנת $1$ ל-$x_1$, $1$ ל-$x_2$ ו-$1$ ל-$x_3$ מספקת את ההסגר השני. לכל אחת מן ההשמות מתאים קודקוד בגרף. ההשמות נותנות ל-$x_1$ ערכים שונים ולכן סותרות; הקודקודים המתאימים יחוברו בקשת.

9. טענה: $3\text{-}SAT\le_p IS$.
   אלגוריתם: האלגוריתם מן הסעיף הקודם.

10. טענה: $SAT\le_p MAX\text{-}IS$.
    אלגוריתם: זהה לזה שראינו בשיעור ברדוקציה מ-$SAT$ ל-$IS$.