נתונות מחלקות הסיבוכיות הבאות. 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 מבצעת הוא לכל היותר 10 lg|x| בכל ריצה על $x\in Σ*$ כמו כן לכל אם $x\in A$ אז כל ריצה של M על x מקבלת. וגם אם $x\notin A$ אז קיימת ריצת של M על x שבה M דוחה. אילו מהטענות הבאות היא התוצאה ביותר היידוע כנכונה?