יהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר…

יהיו $k\in\mathbb N$ ו-$A\subseteq\{0,\ldots,k\}$. נגדיר את הבעיה $kSAT_A$:

קלט: נוסחה בצורת $k$-CNF.
שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-$A$?

לדוגמה, ב-$3SAT_{\{2,3\}}$ נדרש שבכל פסוקית בדיוק שניים או שלושה ליטרלים יקבלו אמת.

1. בטאו את בעיית $kSAT$ הרגילה באמצעות קבוצה מתאימה $A$.
2. הוכיחו כי $kSAT_A\in NP$ לכל $k,A$.
3. הוכיחו כי $kSAT_{\{k\}}\in P$.
4. לכל $k\ge3$, הוכיחו $$kSAT\le_p (k+1)SAT_{\{1,2,\ldots,k\}}.$$
5. לכל $k\ge3$, הוכיחו $$(k+1)SAT_{\{1,2,\ldots,k\}}\le_p kSAT_{\{1,2,\ldots,k-1\}}.$$
6. הסיקו כי $3SAT_{\{1,2\}}$ היא $NP$-שלמה. הסבירו מדוע התוצאה נותרת נכונה גם כאשר בכל פסוקית יש בדיוק שלושה ליטרלים.
7. הוכיחו כי $3SAT_{\{1,3\}}\in P$. רמז: מערכת משוואות לינאריות מעל $\mathbb F_2$.