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

في علم التعقيد الحسابي RP أو Randomized Polynomial time هو قسم المسائل التي تقريرها بوقت حدودي بواسطة آلة تيورنج احتمالية مع الخاصية التالية:

• إذا كان المُدخل جوابه نعم حينها احتمال أن الجواب هو نعم أكبر من ${\frac {1}{2}}$
• إذا كان المُدخل جوابه لا حينها احتمال ان الجواب هو لا هو 1 .

أي انه إذا كان الجواب نعم فهو حتما نعم اما إذا كان الجواب لا فانه باحتمال 1/2 على الأقل ان يكون الجواب لا .

يمكن استبدال الثابت 1/2 بأي عدد لا يساوي 0 اقل من 1 .

تعريف

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

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

علاقات مع اقسام أخرى

• $RP\subseteq NP$ وهذا لاننا يمكن تعريف RP على النحو التالي: مسألة تقرير L تابعة ل-RP إذا يمكن تقريرها بواسطة آلة تيورنج غير قطعية بوقت كثير الحدود حيث أنه يوجد نسبة ثابتة(مثال %50 أو أكثر) من مسارات الحساب التي اجابتها نعم. لذا فان RP تابعة NP حسب هذا التعريف
• $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 .
• $P\subseteq RP$ وذلك لاننا يمكن التفكير عن آلة تيورنج قطعية كثيرة الحدود على أنها آلة احتمالية مع احتمال خطأ 0 .

مبرهنات التكبير

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

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

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

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

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

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

القسم المُكمِل

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

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

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

علاقات مع اقسام أخرى

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

مبرهنات التكبير

كما هنالك مبرهنات تكبير ل-RP بشكل مشابه يمكن أيضا برهنتها ل- co-RP . أي انه:

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

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

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

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

امثلة

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

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

علاقة مع PCP

المقالة الرئيسة: براهين قابلة للفحص بشكل احتمالي

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
• خوارزمية