RL (التعقيد)

تُعرف فئة التعقيد العشوائي في الفضاء اللوغاريتمي ( RL )، ^{[ 1 ]} والتي تُسمى أحيانًا RLP (التعقيد العشوائي في الفضاء اللوغاريتمي والزمن متعدد الحدود)، ^{[ 2 ]،} بأنها فئة من مسائل نظرية التعقيد الحسابي التي يمكن حلها في فضاء لوغاريتمي وزمن متعدد الحدود باستخدام آلات تورينغ الاحتمالية ذات الخطأ أحادي الجانب . وقد سُميت بهذا الاسم قياسًا على فئة RP ، وهي فئة مشابهة لها ولكنها لا تخضع لقيود الفضاء اللوغاريتمي.

لا تقبل خوارزمية التعلم المعزز (RL) بشكل خاطئ أبدًا، ولكن يُسمح لها بالرفض بشكل خاطئ في أقل من ثلث الحالات؛ وهذا ما يُسمى بالخطأ أحادي الجانب . القيمة الثابتة 1/3 اختيارية؛ أي قيمة لـ x حيث 0 < x < 1 تكفي. يمكن تقليل هذا الخطأ بمقدار 2 ^{− p ( x )} مرة لأي دالة كثيرة الحدود p ( x ) دون استخدام وقت يتجاوز وقت كثير الحدود أو مساحة لوغاريتمية، وذلك بتشغيل الخوارزمية بشكل متكرر.

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

أظهر نعوم نيسان في عام 1992 نتيجة إزالة العشوائية الضعيفة التي تحتوي على RL في SC ، ^{[ 3 ]} فئة المشاكل القابلة للحل في وقت متعدد الحدود ومساحة متعددة اللوغاريتمات على آلة تورينج حتمية؛ بعبارة أخرى، بالنظر إلى مساحة متعددة اللوغاريتمات ، يمكن لآلة حتمية محاكاة الخوارزميات الاحتمالية ذات المساحة اللوغاريتمية .

يُعتقد أن RL يساوي L ، أي أن حسابات فضاء اللوغاريتمات ذات الوقت متعدد الحدود يمكن إزالة عشوائيتها تمامًا؛ وقد قدم رينغولد وآخرون في عام 2005 دليلًا رئيسيًا على ذلك. ^{[ 4 ]} ويُعدّ إثبات ذلك بمثابة الكأس المقدسة للجهود المبذولة في مجال إزالة العشوائية غير المشروطة لفئات التعقيد. وكانت خطوة كبيرة إلى الأمام هي برهان عمر رينغولد على أن SL يساوي L.