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

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

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

• נוסחת $CNF$ ספיקה במובן $NAE$ אם קיימת השמה שבה בכל הסגר יש ליטרל שערכו $True$ וליטרל שערכו $False$. עבור $k$ טבעי, $kNAE$ היא שפת נוסחאות $kCNF$ הספיקות במובן $NAE$.
• $MAX\text{-}IS$ היא שפת כל הקידודים $\langle G,k\rangle$ שעבורם הגודל המרבי של קבוצה בלתי תלויה ב-$G$ הוא $k$; כלומר, קיימת קבוצה בלתי תלויה בגודל $k$, ולכל קבוצה בלתי תלויה $U$ ב-$G$ מתקיים $|U|\le k$.

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

2. טענה: $3SAT\le_p4NAE$.
   אלגוריתם: אותה בנייה, אך מחזירים רק את הנוסחה המתקבלת.

3. טענה: $4NAE\le_p3NAE$.
   אלגוריתם: כל הסגר

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

   מוחלף בשני ההסגרים

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

   כאשר לכל הסגר מקורי נוסף משתנה חדש שונה.

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

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

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

   • לכל הסגר של $\varphi$ ולכל השמה למשתניו המספקת אותו, יוגדר קודקוד.
   • כל שני קודקודים המתאימים להשמות של אותו הסגר יחוברו בקשת. בנוסף, יחוברו שני קודקודים מהסגרים שונים אם ההשמות שהם מייצגים סותרות זו את זו.

   למשל, עבור

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

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

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

8. טענה: $SAT\le_p IS$.
   אלגוריתם: בהינתן נוסחת $CNF$ $\varphi$ בעלת $m$ הסגרים, נחזיר $\langle G,m\rangle$. לכל ליטרל בכל הסגר מתאים קודקוד; שני קודקודים מחוברים אם ורק אם הם מייצגים ליטרלים באותו הסגר או מייצגים משתנה ושלילתו.

   למשל, עבור

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

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

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