1. נוסחה בוליאנית מצורת kCNF היא ספיקה במובן NAE ‏(Not\ All\ Equal) אם קיימת השמה שעבורה בכל פסוקית יש ליטרל ש…

נוסחה בוליאנית מצורת $kCNF$ היא ספיקה במובן $NAE$ ‏($Not\ All\ Equal$) אם קיימת השמה שעבורה בכל פסוקית יש ליטרל שערכו $True$ וליטרל שערכו $False$. תהא $kNAE$ שפת כל נוסחאות ה-$kCNF$ שספיקות במובן זה.

1. הוכיחו כי לכל $k$ טבעי, $kNAE\in NP$.
2. הוכיחו: $$3SAT\le_p4NAE\le_p3NAE.$$ הדרכה: ברדוקציה הראשונה הוסיפו משתנה חדש $z$ לכל הפסוקיות. עבור הרדוקציה השנייה היזכרו ברדוקציה מן ההרצאה מ-$SAT$ ל-$3SAT$.

בגרף $G=(V,E)$, קבוצה בלתי-תלויה היא קבוצת קודקודים $S\subseteq V$ כך שאין קשת בין שני קודקודים של $S$. תהא

1. הוכיחו כי $IS\in NP$.
2. נציע רדוקציה מ-$SAT$ ל-$IS$: בהינתן נוסחת $CNF$ ‏$\varphi$ עם $m$ פסוקיות, נחזיר גרף לא מכוון $G$ ואת המספר $m$. קודקודי $G$ הם מופעי הליטרלים בנוסחה - כל מופע הוא קודקוד נפרד. שני קודקודים מחוברים אם הם מופיעים באותה פסוקית, או אם הם מתאימים למשתנה ולשלילתו. הוכיחו את נכונות הרדוקציה ונתחו את זמן ריצתה.
3. תהא $$MAX\text{-}IS= \{\langle G,k\rangle\mid \text{הגודל המרבי של קבוצה בלתי-תלויה ב-}G\text{ הוא }k\}.$$ האם הרדוקציה מן הסעיף הקודם היא רדוקציה מ-$SAT$ ל-$MAX\text{-}IS$? הוכיחו את קביעתכם.