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

נתונות מחלקות הסיבוכיות הבאות. I. המחלקה $C_1$ היא כל מחלקת השפות $A\subseteq Σ*$ עבורן קיימת מכונת טיורינג M וקיים פולינום P כך שלכל $x\in Σ*$, רצה על x בזמן לכל היותר p(|x|), משתמשת בלכל היותר p(|x|) ביטים אקראיים וכמו כן לכל $x\in Σ*, Pr_{r\in{0,1}^{p(|x|)}} [M(x,r) accepts] \ge 1 - 1/2^{|x|}$ אם $x\in A$ וגם $Pr_{r\in{0,1}^{p(|x|)}} [M(x,r) rejects] = 1$ אם $x\notin A II$. המחלקה $C_2$ היא כל מחלקת השפות $A\subseteq Σ*$ עבורן קיימת מכונת טיורינג M וקיים פולינום P כך שלכל $x\in Σ*$, רצה על x בזמן לכל היותר p(|x|), משתמשת בלכל היותר 4 ביטים אקראיים וכמו כן לכל $x\in Σ*, Pr_{r\in{0,1}^4} [M(x,r) accepts] \ge 2/3$ אם $x\in A$ וגם $Pr_{r\in{0,1}^4} [M(x,r) rejects] \ge 2/3$ אם $x\notin A$ אילו מהטענות הבאות ידועה כנכונה?