أر بي (تعقيد حسابي)

مسألة تقرير L تابعة ل- RP إذا يوجد خوارزمية احتمالية,A,وقتها كثير الحدود (polynomial time) بحيث أن:

• لكل ${\displaystyle x\in L}$ يتحقق ${\displaystyle {\mbox{Pr}}[{\mbox{A(x)}}=1]\geq {\frac {1}{2}}}$
• لكل ${\displaystyle x\notin L}$ يتحقق ${\displaystyle {\mbox{Pr}}[{\mbox{A(x)}}=0]=1}$

• ${\displaystyle RP\subseteq NP}$ وهذا لاننا يمكن تعريف RP على النحو التالي : مسألة تقرير L تابعة ل-RP إذا يمكن تقريرها بواسطة آلة تيورنج غير قطعية بوقت كثير الحدود حيث أنه يوجد نسبة ثابتة(مثال %50 أو أكثر) من مسارات الحساب التي اجابتها نعم . لذا فان RP تابعة NP حسب هذا التعريف
• ${\displaystyle RP\subseteq BPP}$ وهذا سهل جدا وذلك لان : فلتكن مسألة L تابعة ل- RP حينها حسب تعريف BPP يجب أن نبين أن هنالك خوارزمية التي تقرر المسألة بحيث أن إذا x∈L حينها Pr[A'(x)=1]≥2/3 واذا x∉L حينها Pr[A'(x)=0]≥2/3 ولكن إذا اخترنا A من تعريف RP فان هذه الصفة تنطبق عليه لذا فان RP ⊆ BPP .
• ${\displaystyle P\subseteq RP}$ وذلك لاننا يمكن التفكير عن آلة تيورنج قطعية كثيرة الحدود على أنها آلة احتمالية مع احتمال خطأ 0 .

وهي تبين أن تكبير نسبة النجاح في الخوارزمية لا تضيف قوة اضافية للقسم بل هو يبقى هو نفسه ونص المبرهنة كالتالي :

فلنفرض أن M هي آلة تيورنج احتمالية التي تقرر المسألة L , وليكن ${\displaystyle 0\leq \varepsilon <1}$ وكذلك :

• x ∈ L حينها ${\displaystyle \varepsilon }$-Pr[M(x)=1] ≥ 1
• x ∉ L حينها Pr[M(x)=0] = 1

حينها لاي ${\displaystyle \varepsilon '}$ بحيث أنه يتحقق : ${\displaystyle 0\leq \varepsilon '<1}$ يوجد 'M آلة تيورنج احتمالية كثيرة حدود أخرى التي تقرر L ويتحقق التالي :

• x ∈ L حينها ${\displaystyle \varepsilon '}$-Pr[M'(x)=1] ≥ 1
• x ∉ L حينها Pr[M'(x)=0] = 1

الفكرة من وراء البرهان هي أننا يمكننا ان نشغل الخوارزمية عدة مرات ( لنقل عدد المرات محدود بواسطة متعدد حدود ) وفحص الاجوبة إذا كان هنالك جواب واحد نعم نجيب نعم خلاف هذا نجيب لا .

القسم المُكمل ل-RP أو co-RP هو قسم المسائل الذي يحقق التالي :

مسألة تقرير L تابعة ل- co-RP إذا يوجد خوارزمية احتمالية,A,وقتها كثير الحدود (polynomial time) بحيث أن:

• لكل ${\displaystyle x\in L}$ يتحقق ${\displaystyle {\mbox{Pr}}[{\mbox{A(x)}}=1]=1}$
• لكل ${\displaystyle x\notin L}$ يتحقق ${\displaystyle {\mbox{Pr}}[{\mbox{A(x)}}=0]\geq 1}$

لعل أهم المسائل التي تم إيجاد برهان انها تابعة ل- RP هي : فحص الاولية : أي باعطائنا رقم طبيعي المُخرج هو هل العدد هو اولي أو قابل للتحليل ؟ أو بشكل رسمي : {Primes={<n>|n ≠ pq , 1<p,q ≤ n هذه المسألة تم البرهنة على أنها في P .

مثال آخر هو فحص تطابق كثيرات الحدود (polynomials) وبواسطة مبرهنة شوارتز-زيبل يمكننا الحصول على خوارزمية عشوائية لذا فان هذه المسألة تتبع القسم Co-RP حسب شوارتز-زيبل . هذه المسألة لا يُعرف أهي تتبع القسم P أو لا .

PCP أو براهين قابلة للفحص بشكل احتمالي هي نظام براهين فيه الفاحص هو آلة تيورنج احتمالية بحيث يسمح بقراءة كمية معينة من البرهان وكذلك عشوائية الفاحص محدودة , نرمز لعدد القراءات من البرهان (q(n وعشوائية الفاحص هي : (r(n حيث أن n هو طول المدخل ونرمز ل-[(PCP[q(n),r(n قسم المسائل التي يمكن تقريرها بنظام PCP كهذا , حينها [(co-RP=PCP[0,poly(n .

لعل أشهر حدسية هي P-NP وفي حال أنَّ NP=P حينها P=RP=co-RP ولكن إذا NP≠P حينها اما RP=P أو RP≠P .

حدسيات أخرى لا يُعرف لها جواب :

• هل BPP=RP ?
• هل co-RP=RP ?
• هل RP=NP ?
• هل co-RP ⊆ NP ?

• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية

• بوابة رياضيات
• بوابة علم الحاسوب