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

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

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

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

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

تعريف

مسألة تقرير 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}$

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

• ${\displaystyle {\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 .
• ${\displaystyle {\mbox{co-RP}}\subseteq {\mbox{co-NP}}}$ وهذا لانَّ ${\displaystyle {\mbox{RP}}\subseteq {\mbox{NP}}}$
• ${\displaystyle {\mbox{P}}\subseteq {\mbox{co-RP}}}$ يمكن النظر ل- P على أنها آلة تيورنج احتمالية لا تخطأ ابدا .

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

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

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

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

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

• x ∈ L حينها Pr[M'(x)=1] = 1
• x ∉ L حينها ${\displaystyle \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
• خوارزمية

موسوعات ذات صلة :

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