البرمجة التفاعلية (التعقيد)

في نظرية التعقيد الحسابي ، يُعد وقت كثير الحدود العشوائي ( RP ) فئة التعقيد لمشاكل القرار التي توجد لها آلة تورينج احتمالية بهذه الخصائص:

• يعمل دائمًا في وقت متعدد الحدود بالنسبة لحجم الإدخال
• إذا كانت الإجابة الصحيحة هي لا، فسيتم إرجاع لا دائمًا
• إذا كانت الإجابة الصحيحة هي نعم، فإنها تعيد نعم باحتمالية لا تقل عن 1/2 (وإلا فإنها تعيد لا).

بمعنى آخر، يُسمح للخوارزمية برمي عملة عشوائية تمامًا أثناء تشغيلها. الحالة الوحيدة التي يمكن أن تُرجع فيها الخوارزمية "نعم" هي إذا كانت الإجابة الفعلية "نعم"؛ لذا، إذا توقفت الخوارزمية وأنتجت "نعم"، فإن الإجابة الصحيحة هي "نعم" بالتأكيد؛ ومع ذلك، يمكن أن تتوقف الخوارزمية بـ"لا" بغض النظر عن الإجابة الفعلية. أي، إذا أرجعت الخوارزمية "لا"، فقد تكون خاطئة.

يُطلق بعض المؤلفين على هذه الفئة اسم R ، على الرغم من أن هذا الاسم يُستخدم بشكل أكثر شيوعًا لفئة اللغات المتكررة .

إذا كانت الإجابة الصحيحة هي "نعم"، وتم تشغيل الخوارزمية n مرة، وكانت نتيجة كل تشغيل مستقلة إحصائيًا عن الأخرى، فإنها ستُرجع "نعم" مرة واحدة على الأقل باحتمالية لا تقل عن 1 - 2 ^{- n} . لذا، إذا تم تشغيل الخوارزمية 100 مرة، فإن احتمال إعطائها إجابة خاطئة في كل مرة أقل من احتمال تلف ذاكرة الحاسوب الذي يُشغل الخوارزمية بفعل الأشعة الكونية. ^{[ 1 ]} وبهذا المعنى، إذا توفر مصدر للأرقام العشوائية، فإن معظم الخوارزميات في البرمجة العشوائية تُعدّ عملية للغاية.

الكسر 1/2 في التعريف اختياري. ستحتوي المجموعة RP على نفس المسائل تمامًا، حتى لو استُبدل 1/2 بأي احتمال ثابت غير صفري أقل من 1؛ هنا، الثابت يعني مستقل عن مُدخلات الخوارزمية.

تكون اللغة L في RP إذا وفقط إذا وُجدت آلة تورينغ احتمالية M ، بحيث

• يتم تشغيل M في وقت متعدد الحدود على جميع المدخلات
• لكل قيمة x في L ، تُخرج M القيمة 1 باحتمالية أكبر من أو تساوي 1/2
• لكل x ليس في L ، فإن M تُخرج 0

بدلاً من ذلك، يمكن تعريف RP باستخدام آلات تورينغ الحتمية فقط. تكون اللغة L في RP إذا وفقط إذا وُجد متعدد حدود p وآلة تورينغ حتمية M ، بحيث

• يتم تشغيل M في وقت متعدد الحدود p على جميع المدخلات
• لكل x في L ، نسبة السلاسل y ذات الطول p (| x |) التي تحقق ⁠${\displaystyle M(x,y)=1}$أكبر من أو يساوي 1/2
• لكل x ليس في L ، ولكل سلسلة y بطول p (| x |) ،${\displaystyle M(x,y)=0}$⁠

في هذا التعريف، يُمثل النص y ناتج رميات العملة العشوائية التي كانت ستُجريها آلة تورينغ الاحتمالية. يُفضل هذا التعريف في بعض التطبيقات لأنه لا يُشير إلى آلات تورينغ الاحتمالية.

ينص تعريف البرمجة العشوائية (RP) على أن الإجابة بنعم صحيحة دائمًا، وأن الإجابة بلا قد تكون خاطئة، إذ يمكن أن تُرجع حالة الإجابة بنعم إجابة بلا. أما فئة التعقيد co-RP فهي مكملة، حيث قد تكون الإجابة بنعم خاطئة بينما تكون الإجابة بلا صحيحة دائمًا.

يصف الصنف BPP الخوارزميات التي قد تُعطي إجابات خاطئة في حالتي "نعم" و"لا"، وبالتالي فهو يشمل كلاً من RP و co-RP . يُطلق على تقاطع المجموعتين RP و co-RP اسم ZPP . وكما يُطلق على RP أحيانًا اسم R ، يستخدم بعض المؤلفين اسم co-R بدلاً من co-RP .

مشكلة لم تُحل في علوم الحاسوب

⁠${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {RP}}}$⁠

المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

P هي مجموعة جزئية من RP ، وهي بدورها مجموعة جزئية من NP . وبالمثل، P هي مجموعة جزئية من co-RP ، وهي بدورها مجموعة جزئية من co-NP . ولا يُعرف ما إذا كانت هذه الاحتواءات صارمة. مع ذلك، إذاصحّت الفرضية الشائعة P = BPP ، فإن RP و co-RP و P تتداخل (أي تصبح جميعها متساوية). وبافتراض أن P ≠ NP ، فإن هذا يعني أن RP محتواة تمامًا في NP . ولا يُعرف ما إذا كانت RP = co-RP ، أو ما إذا كانت RP مجموعة جزئية من تقاطع NP و co-NP ، على الرغم من أن هذا يُستنتج ضمنيًا من P = BPP .

من الأمثلة الطبيعية على مشكلة في co-RP غير معروفة حاليًا بأنها في P اختبار هوية كثير الحدود ، وهي مشكلة تحديد ما إذا كان تعبير حسابي متعدد المتغيرات معين على الأعداد الصحيحة هو كثير حدود صفري. على سبيل المثال، x · x − y · y − ( x + y )·( x − y ) هو كثير حدود صفري، بينما x · x + y · y ليس كذلك.

يُعدّ تعريف RP ، الذي قد يكون أسهل استخدامًا في بعض الأحيان، مجموعة المسائل التي يمكن لآلات تورينغ غير الحتمية التعرف عليها ، حيث تقبل الآلة المسألة إذا وفقط إذا قبلتها نسبة ثابتة على الأقل من مسارات الحساب، بغض النظر عن حجم المدخلات. أما NP، من ناحية أخرى، فلا تحتاج إلا إلى مسار قبول واحد، والذي قد يشكل نسبة ضئيلة جدًا من المسارات. هذا التعريف يجعل حقيقة أن RP هي مجموعة جزئية من NP أمرًا بديهيًا.

• خوارزمية عشوائية

• لعب الأدوار في حديقة حيوانات التعقيد