יהי [0,1]. נגדיר: - C 1 היא מחלקת השפות A שעבורן קיימת מכונת טיורינג הסתברותית M הרצה בזמן פולינומי, כך שלכל x…

יהי $\alpha\in[0,1]$. נגדיר:

• $C_1$ היא מחלקת השפות $A$ שעבורן קיימת מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי, כך שלכל $x$:
  • אם $x\in A$, אז $\Pr[M\text{ accepts }x]\ge\alpha$;
  • אם $x\notin A$, אז $\Pr[M\text{ rejects }x]=1$.
• $C_2$ היא מחלקת השפות $A$ שעבורן קיימת מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי, כך שלכל $x$:
  • אם $x\in A$, אז $\Pr[M\text{ accepts }x]\ge\alpha$;
  • אם $x\notin A$, אז $\Pr[M\text{ rejects }x]\ge\alpha$.
• $C_3$ היא מחלקת השפות $A$ שעבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי, כך שלכל $x$:
  • אם $x\in A$, אז $$\Pr_{r\in\{0,1\}^5}[M\text{ accepts }(x,r)]\ge\alpha;$$
  • אם $x\notin A$, אז $$\Pr_{r\in\{0,1\}^5}[M\text{ rejects }(x,r)]\ge\alpha.$$
• $C_4$ היא מחלקת השפות $A$ שעבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי וקיים פולינום $p$, כך שלכל $x$:
  • אם $x\in A$, אז $$\Pr_{r\in\{0,1\}^{p(|x|)}}[M\text{ accepts }(x,r)] \ge1-\frac1{2^{p(|x|)+1}};$$
  • אם $x\notin A$, אז $$\Pr_{r\in\{0,1\}^{p(|x|)}}[M\text{ rejects }(x,r)] \ge1-\frac1{2^{p(|x|)+1}}.$$

עבור כל טענה קבעו אם היא נכונה, שגויה או שקולה לטענה פתוחה:

1. אם $\alpha=1/10$, אז $C_1=RP$.
2. אם $\alpha=1/10$, אז $C_2=BPP$.
3. אם $\alpha=1$, אז $C_2=P$.
4. אם $\alpha=2/3$, אז $C_3=P$.
5. $C_4=NP$.