هل أي خوارزمية عشوائية توزيع احتمالية على مجموعة الخوارزميات الحتمية؟

Question

إذا كان هناك مجموعة محدودة من حالات الحجم N ومجموعة الخوارزميات الحتمية (المعقولة) FINIT.

هل يمكن اعتبار أي خوارزمية عشوائية توزيع احتمالية على مجموعة الخوارزميات الحتمية؟وإذا كانت الإجابة بنعم، لماذا؟

Answer 1

يمكنك التفكير في خوارزمية عشوائية على أنها الوصول إلى متغير عشوائي $ \ mathbf {r} $ ، والتي تبلغ قراراتها العشوائية.لأي تحديد $ \ mathbf {r} $ ، يمكنك الحصول على خوارزمية حتمية، وبهذه الطريقة يمكنك عرض الخوارزمية الأصلية ذات العشوائية كتوزيع على الخوارزميات الحتمية.

كمثال، فكر في الخوارزمية العشوائية لحل MAX-3SAT.الخوارزمية تختار مهمة عشوائية.يمكنك التفكير في هذه المهمة كما هو محدد بواسطة $ \ mathbf {r} $ .أي مهمة معينة تتوافق مع خوارزمية حتمية، والخوارزمية الأصلية الأصلية هي مجرد توزيع موحد على هذه الخوارزميات الحتمية هذه.