לכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהיא שייכת מבין המחלקות…

לכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהיא שייכת מבין המחלקות $P,NP,coNP,EXP$. הוכיחו את קביעותיכם.

1. קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$.
   שאלה: האם קיימת השמה שאינה מספקת את $\varphi$?
2. קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$.
   שאלה: האם קיימת השמה שמספקת את $\varphi$?
3. קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$.
   שאלה: האם לכל היותר השמה אחת מספקת את $\varphi$?
4. קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$.
   שאלה: האם לכל היותר השמה אחת אינה מספקת את $\varphi$?
5. קלט: זוג נוסחאות בוליאניות $\varphi_1,\varphi_2$ מצורת $CNF$.
   שאלה: האם $\varphi_1$ ספיקה וגם $\varphi_2$ אינה ספיקה?