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

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