עבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את…

עבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את $NP$, מוכלת ב-$NP$, ושווה ל-$NP$ - אם הדבר ידוע. הוכיחו את קביעותיכם.

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

1. $C_1$: מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיימים פולינום $p$ ומכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$: $$x\in A \iff \exists w\in\{0,1\}^{p(|x|)}:\ M(x,w)=F.$$
2. $C_2$: מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיימים פולינום $p$ ומכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$:
   • אם $x\in A$, קיים $w\in\{0,1\}^{p(|x|)}$ שעבורו $M(x,w)=T$;
   • אם $x\notin A$, קיים $w\in\{0,1\}^{p(|x|)}$ שעבורו $M(x,w)=F$.
3. $C_3$: מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיימים פולינום $p$ ומכונת טיורינג אי-דטרמיניסטית $M$, כך שלכל $x\in\Sigma^*$:
   • אם $x\in A$, אז בכל תסריט ריצה של $M$ על $x$ המכונה עוצרת בתוך לכל היותר $p(|x|)$ צעדים, ומגיעה למצב מקבל או דוחה;
   • אם $x\notin A$, המכונה $M$ אינה עוצרת על $x$ באף תסריט ריצה.