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

יהי $\alpha\in[0,1]$. נגדיר את מחלקות הסיבוכיות הבאות:

• $C_1$ היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x\in\Sigma^*$:
  • אם $x\in A$, אז $\Pr[M\text{ accepts }x]\ge\alpha$;
  • אם $x\notin A$, אז $\Pr[M\text{ rejects }x]=1$.
• $C_2$ היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג הסתברותית $M$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x\in\Sigma^*$:
  • אם $x\in A$, אז $\Pr[M\text{ accepts }x]\ge\alpha$;
  • אם $x\notin A$, אז $\Pr[M\text{ rejects }x]\ge\alpha$.
• $C_3$ היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט, כך שלכל $x\in\Sigma^*$:
  • אם $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$ היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג דטרמיניסטית $M$ הרצה בזמן פולינומי בגודל הקלט וקיים פולינום $p$, כך שלכל $x\in\Sigma^*$:
  • אם $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=\frac1{10}$, אז $C_1=RP$.
2. אם $\alpha=\frac1{10}$, אז $C_2=BPP$.
3. אם $\alpha=1$, אז $C_2=P$.
4. אם $\alpha=\frac23$, אז $C_3=P$.
5. $C_4=NP$.