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

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

1. $C_1$ — מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיים $c\ge1$ וקיימת מכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$: $$x\in A \iff \text{קיים }w\in\{0,1\}^{|x|^c}\text{ שעבורו }M\text{ דוחה את }(x,w).$$
2. $C_2$ — מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיים $c\ge1$ וקיימת מכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$:
   • אם $x\in A$, אז קיים $w\in\{0,1\}^{|x|^c}$ שעבורו $M$ מקבלת את $(x,w)$;
   • אם $x\notin A$, אז קיים $w\in\{0,1\}^{|x|^c}$ שעבורו $M$ דוחה את $(x,w)$.
3. $C_3$ — מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיים $c\ge1$ וקיימת מכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$: $$x\in A \iff \text{קיים }w\in\{0,1\}^{|x|^c}\text{ שעבורו }M\text{ מקבלת את }(x,w).$$
4. $C_4$ — מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיים $c\ge1$ וקיימת מכונת טיורינג אי־דטרמיניסטית $M$, כך שלכל $x\in\Sigma^*$:
   • אם $x\in A$, אז קיימת ריצה של $M$ על הקלט $x$ שבה היא עוצרת תוך לכל היותר $|x|^c$ צעדים;
   • אם $x\notin A$, אז המכונה $M$ אינה עוצרת על $x$ באף ריצה.
5. $C_5$ — מחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיים $c\ge1$ וקיימת מכונת טיורינג אי־דטרמיניסטית $M$ בעלת זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$ מספר הבחירות האי־דטרמיניסטיות בריצה על $x$ אינו עולה על $c\cdot\lg|x|$ באף ריצה, ובנוסף:
   • אם $x\in A$, אז קיימת ריצה של $M$ על הקלט $x$ שבה היא מגיעה למצב מקבל;
   • אם $x\notin A$, אז $M$ דוחה את $x$ בכל ריצה.