נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת דטרמיניסטית טיורינג M וק…

נתונות מחלקות הסיבוכיות הבאות. I. המחלקה $C_1$ היא מחלקת כל השפות $A\subseteq Σ*$ עבור קיימת מכונת דטרמיניסטית טיורינג M וקיים פולינום p כך שלכל $x\in Σ*, x\in Σ*$ וכמו כן לזמן ריצה יותר לכל $x\in Σ*$ אם $x\in A$ אז לכל $w\in{0,1}^{p(|x|)}$ מתקיים: אם תו הראשון ב w הוא 0 אז M(x,w) תתקבל אם וגם תו הראשון ב w הוא 1 אז M(x,w) נדחה. כמו כן אם $x\notin A$ אז לכל $w\in{0,1}^{p(|x|)}$ מתקיים: אם תו הראשון ב w הוא 0 אז M(x,w) נדחה וגם אם תו הראשון ב w הוא 1 אז M(x,w) תתקבל. II. המחלקה $C_2$ היא מחלקת כל השפות $A\subseteq Σ*$ עבור קיימת מכונת דטרמיניסטית טיורינג M וקיים פולינום p כך שלכל $x\in Σ*, x\in Σ*$ וכמו כן לזמן ריצה יותר לכל $x\in Σ*$ אם $x\in A$ אז קיים $w\in{0,1}^{p(|x|)}$ כך ש M(x,w) תתקבל וגם אם $x\notin A$ אז קיים $w\in{0,1}^{p(|x|)}$ כך ש M(x,w) נדחה. III. המחלקה $C_3$ היא מחלקת כל השפות $A\subseteq Σ*$ עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים פולינום p כך שלכל $x\in Σ*$, אם $x\in A$ אז קיימת ריצה מקבלת של M על x שבה מספר העצעים שM מבצע גדול מ p(|x|), וגם אם $x\notin A$ אז כל ריצה של M על x נעצרת לאחר עצעים p(|x|) לכל היותר. איזו מהטענות הבאות ידוע כנכונה? (שימו לב שמשמעות הסימון 2^Σ* היא קבוצת כל השפות.)