المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من RP (تعقيد حسابي))
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)

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

  • اذا كان المُدخل جوابه نعم حينها احتمال أن الجواب هو نعم أكبر من
  • اذا كان المُدخل جوابه لا حينها احتمال ان الجواب هو لا هو 1 .

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

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

تعريف[عدل]

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

  • لكل يتحقق
  • لكل يتحقق

علاقات مع اقسام اخرى[عدل]

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

مبرهنات التكبير[عدل]

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

فلنفرض أن M هي آلة تيورنج احتمالية التي تقرر المسألة L , وليكن وكذلك :

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

حينها لاي بحيث أنه يتحقق : يوجد 'M آلة تيورنج احتمالية كثيرة حدود أخرى التي تقرر L ويتحقق التالي :

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

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

القسم المُكمِل[عدل]

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

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

  • لكل يتحقق
  • لكل يتحقق

علاقات مع اقسام اخرى[عدل]

  • فلتكن مسألة 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 .
  • وهذا لانَّ
  • يمكن النظر ل- P على أنها آلة تيورنج احتمالية لا تخطأ ابدا .

مبرهنات التكبير[عدل]

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

فلنفرض أن M هي آلة تيورنج احتمالية التي تقرر المسألة L , وليكن وكذلك :

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

حينها لاي بحيث أنه يتحقق : يوجد 'M آلة تيورنج احتمالية كثيرة حدود أخرى التي تقرر L ويتحقق التالي :

  • x ∈ L حينها Pr[M'(x)=1] = 1
  • x ∉ L حينها -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 ?

انظر أيضا[عدل]