תהא D מחלקת השפות A Σ* עבורן קיימים מכונת טיורינג M עם זמן ריצה פולינומיאלי ופולינום q כך שלכל x Σ* מתקיים: אם…

תהא D מחלקת השפות $A \subseteq Σ*$ עבורן קיימים מכונת טיורינג M עם זמן ריצה פולינומיאלי ופולינום q כך שלכל $x \in Σ*$ מתקיים: אם $x \in A$ אז Pr_{r ~ {0,1}^{q(|x|)}}[M(x,r) = True] = 1 אם $x \notin A$ אז Pr_{r ~ {0,1}^{q(|x|)}}[M(x,r) = False] ≥ 1/(2^{q(|x|)}) מבין המחלקות הבאות, מהי המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא מכילה את D?