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

נתונות מחלקות הסתביכויות הבאות. I. המחלקה $C_1$ היא כל השפות $A\subseteq Σ*$ עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים $c\ge1$ כך שלכל $x\in Σ*$, אם $x\in A$ אז כל ריצה של M על x עוצרת אחרי לכל היותר $|x|^c$ צעדים, וגם אם $x\notin A$ אז קיימת ריצה של M על x שאינה עוצרת. II. המחלקה $C_2$ היא כל השפות $A\subseteq Σ*$ עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M עם זמן ריצה פולינומי כך שלכל $x\in Σ*$ מספר הבחירות האי-דטרמיניסטיות ש M מבצעת הוא לכל היותר lg|x| בכל ריצה על x. כמו כן לכל $x\in Σ*$ אם $x\in A$ אז קיימת ריצה תמימת מקבלת של M על x. וגם אם $x\notin A$ אז כל ריצה של M על x דוחה. איזו מהטענות הבאות ידועה כנכונה?