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

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