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

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

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