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

עבור $0<\alpha<1$ נתונות מחלקות הסיבוכיות הבאות.

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

אם $x\in A$ אז $\Pr_{r\in\{0,1\}^{p(|x|)}}\left[M\ accepts\ (x,r)\right]\ge\alpha$

וגם אם $x\notin A$ אז $\Pr_{r\in\{0,1\}^{p(|x|)}}\left[M\ rejects\ (x,r)\right]=1$

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

אם $x\in A$ אז $\Pr_{r\in\{0,1\}^{p(|x|)}}\left[M\ accepts\ (x,r)\right]\ge\alpha$

וגם אם $x\notin A$ אז $\Pr_{r\in\{0,1\}^{p(|x|)}}\left[M\ rejects\ (x,r)\right]\ge\alpha$

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