أر بي (تعقيد حسابي)
المحتويات
على سبيل التعريف، في علم التعقيد الحسابي RP أو Randomized Polynomial time هو قسم المسائل التي تقريرها بوقت حدودي بواسطة آلة تيورنج احتمالية مع الخاصية التالية:
إضافةً إلى ذلك، أي انه إذا كان الجواب نعم فهو حتما نعم اما إذا كان الجواب لا فانه باحتمال 1/2 على الأقل ان يكون الجواب لا .
وفي هذا السياق، إذا كان المُدخل جوابه نعم حينها احتمال أن الجواب هو نعم أكبر من
ومن جهة أخرى، إذا كان المُدخل جوابه لا حينها احتمال ان الجواب هو لا هو 1 .
يمكن استبدال الثابت 1/2 بأي عدد لا يساوي 0 اقل من 1 .
القسم المُكمِل
ومن جهة أخرى، القسم المُكمل ل-RP أو co-RP هو قسم المسائل الذي يحقق التالي:
لكل يتحقق
لكل يتحقق
في هذا الإطار، مسألة تقرير L تابعة ل- co-RP إذا يوجد خوارزمية احتمالية،A, وقتها كثير الحدود (polynomial time) بحيث أن:
x ∉ L حينها Pr[M'(x)=0] = 1
وفي هذا الصدد، الفكرة من وراء البرهان هي أننا يمكننا ان نشغل الخوارزمية عدة مرات (لنقل عدد المرات محدود بواسطة متعدد حدود) وفحص الاجوبة إذا كان هنالك جواب واحد نعم نجيب نعم خلاف هذا نجيب لا .
تعريف
لكل يتحقق
لكل يتحقق
في هذا الإطار، مسألة تقرير L تابعة ل- RP إذا يوجد خوارزمية احتمالية،A, وقتها كثير الحدود (polynomial time) بحيث أن:
x ∉ L حينها -Pr[M(x)=0] ≥ 1
x ∉ L حينها -Pr[M'(x)=0] ≥ 1
x ∈ L حينها Pr[M'(x)=1] = 1
كذلك، حينها لاي بحيث أنه يتحقق: يوجد 'M آلة تيورنج احتمالية كثيرة حدود أخرى التي تقرر L ويتحقق التالي:
x ∉ L حينها Pr[M(x)=0] = 1
x ∈ L حينها -Pr[M'(x)=1] ≥ 1
وفي هذا الصدد، حينها لاي بحيث أنه يتحقق: يوجد 'M آلة تيورنج احتمالية كثيرة حدود أخرى التي تقرر L ويتحقق التالي:
قسم تعقيد
مسألة P=NP
نظرية التعقيد الحسابي.
مبرهنات التكبير
- كما هنالك مبرهنات تكبير ل-RP بشكل مشابه يمكن كذلك برهنتها ل- co-RP . أي انه:
- فلنفرض أن M هي آلة تيورنج احتمالية التي تقرر المسألة L , وليكن وكذلك:
- x ∈ L حينها Pr[M(x)=1] = 1
وهذا لانَّ
يمكن النظر ل- P على أنها آلة تيورنج احتمالية لا تخطأ ابدا.
امثلة
لعل أهم المسائل التي تم إيجاد برهان انها تابعة ل- RP هي:
وعلى صعيد آخر، مثال آخر هو فحص تطابق كثيرات الحدود (polynomials) وبواسطة مبرهنة شوارتز-زيبل يمكننا الحصول على خوارزمية عشوائية لذا فان هذه المسألة تتبع القسم Co-RP حسب شوارتز-زيبل. هذه المسألة لا يُعرف أهي تتبع القسم P أو لا.
كذلك، فحص الاولية: أي باعطائنا رقم طبيعي المُخرج هو هل العدد هو اولي أو قابل للتحليل؟ أو بشكل رسمي: {Primes={|n ≠ pq , 1<p,q ≤ n هذه المسألة تم البرهنة على أنها في P .
علاقات مع اقسام أخرى
في هذا الإطار، وهذا سهل جدا وذلك لان: فلتكن مسألة L تابعة ل- RP حينها حسب تعريف BPP يجب أن نبين أن هنالك خوارزمية التي تقرر المسألة بحيث أن إذا x∈L حينها Pr[A'(x)=1]≥2/3 واذا x∉L حينها Pr[A'(x)=0]≥2/3 ولكن إذا اخترنا A من تعريف RP فان هذه الصفة تنطبق عليه لذا فان RP ⊆ BPP .
كذلك، وهذا لاننا يمكن تعريف RP على النحو التالي: مسألة تقرير L تابعة ل-RP إذا يمكن تقريرها بواسطة آلة تيورنج غير قطعية بوقت كثير الحدود حيث أنه يوجد نسبة ثابتة(مثال %50 أو أكثر) من مسارات الحساب التي اجابتها نعم. لذا فان RP تابعة NP حسب هذا التعريف
في هذا الإطار، وذلك لاننا يمكن التفكير عن آلة تيورنج قطعية كثيرة الحدود على أنها آلة احتمالية مع احتمال خطأ 0 .
علاقات مع اقسام أخرى
وفي هذا الصدد، فلتكن مسألة 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 .
علاقة مع PCP
في هذا الإطار، PCP أو براهين قابلة للفحص بشكل احتمالي هي نظام براهين فيه الفاحص هو آلة تيورنج احتمالية بحيث يسمح بقراءة كمية معينة من البرهان وكذلك عشوائية الفاحص محدودة، نرمز لعدد القراءات من البرهان (q(n وعشوائية الفاحص هي: (r(n حيث أن n هو طول المدخل ونرمز ل-[(PCP[q(n),r(n قسم المسائل التي يمكن تقريرها بنظام PCP كهذا، حينها [(co-RP=PCP[0,poly(n .
مبرهنات التكبير
علاوةً على ذلك، فلنفرض أن M هي آلة تيورنج احتمالية التي تقرر المسألة L , وليكن وكذلك:
x ∈ L حينها -Pr[M(x)=1] ≥ 1
من جهة ثانية، وهي تبين أن تكبير نسبة النجاح في الخوارزمية لا تضيف قوة اضافية للقسم بل هو يبقى هو نفسه ونص المبرهنة كالتالي:
حدسيات
- حدسيات أخرى لا يُعرف لها جواب:
- هل BPP=RP ?
- هل co-RP=RP ?
- هل RP=NP ?
- هل co-RP ⊆ NP ?
- مراجع
- انظر كذلك
من جانب آخر، لعل أشهر حدسية هي P-NP وفي حال أنَّ NP=P حينها P=RP=co-RP ولكن إذا NP≠P حينها اما RP=P أو RP≠P .
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟