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

נתונות מחלקות הסיבוכיות הבאות.

I. המחלקה $C_1$ היא מחלקת כל השפות $A\subseteq\Sigma^*$ עבורן קיימת מכונת טיורינג אי-דטרמיניסטית $M$ וקיים פולינום $p$ כך שלכל $x\in\Sigma^*$,

אם $x\in A$ אז כל ריצה של $M$ על $x$ מקבלת ועוצרת אחרי לכל היותר $p(|x|)$ צעדים,

וגם אם $x\notin A$ אז קיימת ריצה של $M$ על $x$ שאינה עוצרת.

II. המחלקה $C_2$ היא מחלקת כל השפות $A\subseteq\Sigma^*$ עבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט וקיים פולינום $p$ כך שלכל $x\in\Sigma^*$,

אם $x\in A$ אז לכל $w\in\{0,1\}^{p(|x|)}$ מתקיים כי $M$ דוחה את $(x,w)$,

וגם אם $x\notin A$ אז קיים $w\in\{0,1\}^{p(|x|)}$ כך ש-$M$ מקבלת את $(x,w)$.

נתונות הטענות הבאות:

i. $C_1=C_2$.

ii. הטענה $C_1=NP$ שקולה לשאלה פתוחה.

iii. $C_1\subseteq NP$.

אילו מהטענות הנתונות ידועות כנכונות?