לכל טענה קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה, והוכיחו את קביעתכם. השפה SAT-UNSAT היא שפת הזוג…

לכל טענה קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה, והוכיחו את קביעתכם.

השפה $SAT\text{-}UNSAT$ היא שפת הזוגות $(\varphi_1,\varphi_2)$ של נוסחאות בוליאניות מצורת $CNF$ כך ש-$\varphi_1$ ספיקה ו-$\varphi_2$ אינה ספיקה.

1. לכל שפה $PSPACE$-קשה $A$ מתקיים $PSPACE\subseteq P^A$.
2. לכל שפה $A\in PSPACE$ מתקיים $PSPACE\subseteq P^A$.
3. לכל שפה $A\in PSPACE$ מתקיים $P^A\subseteq PSPACE$.
4. קיימת שפה $A\in PSPACE$ המקיימת $PSPACE\subsetneq PSPACE^A$.
5. המחלקה $P^{SAT\text{-}UNSAT}$ סגורה לרדוקציות זמן פולינומיאלי.
6. $P=NP$ אם ורק אם $P=P^{SAT\text{-}UNSAT}$.
7. $P^{SAT}\subsetneq P^{SAT\text{-}UNSAT}$.
8. $P^{SAT\text{-}UNSAT}\subseteq\Sigma_2$.
9. $PSPACE^{SAT\text{-}UNSAT}=EXPSPACE^{SAT\text{-}UNSAT}$.
10. $PSPACE^{EXPCOM}=PSPACE$.
11. לכל שפה $A$, אם $A\le_p SAT$ אז $A\in P^{SAT}$.
12. לכל שפה $A$, אם $A\in P^{SAT}$ אז $A\le_p SAT$.
13. לכל שפה בינארית $B\subseteq\{0,1\}^*$ מתקיים $$\left\{0^n\ \middle|\ \left|B\cap\{0,1\}^n\right|<2^n\right\}\in NP^B.$$