1. הוכיחו כי RP NP. 2. הוכיחו כי BPP PSPACE. 3. הוכיחו כי מחלקת הסיבוכיות RP סגורה לחיתוך, כלומר שאם A,B RP אז…

1. הוכיחו כי $RP\subseteq NP$.

2. הוכיחו כי $BPP\subseteq PSPACE$.

3. הוכיחו כי מחלקת הסיבוכיות $RP$ סגורה לחיתוך, כלומר שאם $A,B\in RP$ אז $A\cap B\in RP$.

4. זהו את מחלקות הסיבוכיות שלהלן והוכיחו את קביעותיכם.

   1. $C_1$ — מחלקת השפות $A$ שעבורן קיימים קבוע $c$ ומכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומיאלי, כך שלכל $x\in A$ מתקיים $$\Pr_{r\in\{0,1\}^{c\log_2|x|}}[M(x,r)=T]=1,$$ ולכל $x\notin A$ מתקיים $$\Pr_{r\in\{0,1\}^{c\log_2|x|}}[M(x,r)=F]\ge\frac13.$$
   2. $C_2$ — מחלקת השפות $A$ שעבורן קיימים פולינום $p$ ומכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומיאלי, כך שלכל $x\in A$ מתקיים $$\Pr_{r\in\{0,1\}^{p(|x|)}}[M(x,r)=T]\ge\frac1{|x|^3},$$ ולכל $x\notin A$ מתקיים $$\Pr_{r\in\{0,1\}^{p(|x|)}}[M(x,r)=F]=1.$$
   3. $C_3$ — מחלקת השפות $A$ שעבורן קיימים פולינום $p$ ומכונת טיורינג דטרמיניסטית $M$ בעלת זמן ריצה פולינומיאלי, כך שלכל $x\in A$ מתקיים $$\Pr_{r\in\{0,1\}^{p(|x|)}}[M(x,r)=T]=1,$$ ולכל $x\notin A$ מתקיים $$\Pr_{r\in\{0,1\}^{p(|x|)}}[M(x,r)=F]\ge2^{-p(|x|)}.$$

רמז: מספר הטענות הנכונות, מספר הטענות שאינן נכונות ומספר הטענות ששקולות לשאלות פתוחות הם כולם מספרים ראשוניים.