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

נתונות מחלקות הסיבוכיות הבאות. I. המחלקה $C_1$ היא מחלקת כל השפות A ⊆ Σ^* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים פולינום P כך שלכל x ∈ Σ^*, אם $x \in A$ אז קיימת ריצה של M על x העוצרת ומקבלת אחרי לכל היותר p(|x|) צעדים, וגם אם $x \notin A$ אז קיימת ריצה של M על x העוצרת ודוחה אחרי לכל היותר p(|x|) צעדים. II. המחלקה $C_2$ היא מחלקת כל השפות A ⊆ Σ^* עבור קיימת מכונת טיורינג דטרמיניסטית M הרצה בזמן פולינומי בגודל הקלט וקיים פולינום P כך שלכל x ∈ Σ^*, אם $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. NP \subseteq C_1 \cap C_2$. אילו מהטענות הנתונות ידועות כנכונות?