לפניכם 2 מחלקות סיבוכיות: • C 1 – מחלקת השפות A * עבורן קיים c 1 כך שקיימת מכונת טיורינג אי-דטרמיניסטית M, כך…

לפניכם 2 מחלקות סיבוכיות: • $C_1$ – מחלקת השפות $A\subseteq\Sigma^*$ עבורן קיים $c\ge 1$ כך שקיימת מכונת טיורינג אי-דטרמיניסטית $M$, כך שלכל $x\in\Sigma^*$ מתקיים: אם $x\in A$ אז קיימת ריצה של המכונה $M$ על הקלט $x$ שבה היא עוצרת תוך $O(|x|^c)$ צעדים, ואם $x\notin A$ אז המכונה $M$ אינה עוצרת על $x$ באף ריצה. • $C_2$ – מחלקת השפות $A\subseteq\Sigma^*$ כך שקיימת מכונת טיורינג דטרמיניסטית $M$ עם זמן ריצה פולינומי, כך שלכל $x\in\Sigma^*$ מתקיים: $x\in A$ אם ורק אם קיים $w\in\{0,1\}^{\lg|x|}$ עבורו $M$ מקבלת את $(x,w)$. איזו מהטענות הבאות ידועה כנכונה?