ZPP (التعقيد)

في نظرية التعقيد ، تُعرف ZPP ( زمن متعدد الحدود الاحتمالي بدون خطأ ) بأنها فئة التعقيد للمسائل التي توجد لها آلة تورينج احتمالية بهذه الخصائص:

• دائماً ما يُرجع الإجابة الصحيحة بنعم أو لا.
• زمن التشغيل متعدد الحدود في المتوسط ​​لكل مدخل.

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

بدلاً من ذلك، يمكن تعريف ZPP على أنها فئة المشاكل التي توجد لها آلة تورينج احتمالية بهذه الخصائص:

• يعمل دائماً في وقت متعدد الحدود.
• يُرجع إجابة بنعم أو لا أو لا أعرف.
• الإجابة دائماً إما "لا أعرف" أو الإجابة الصحيحة.
• يعيد البرنامج "لا أعرف" باحتمالية لا تتجاوز 1/2 لكل مدخل (والإجابة الصحيحة في غير ذلك).

التعريفان متكافئان.

يعتمد تعريف ZPP على آلات تورينج الاحتمالية، ولكن للتوضيح، تجدر الإشارة إلى أن فئات التعقيد الأخرى المبنية عليها تشمل BPP و RP . أما فئة BQP فتعتمد على آلة أخرى ذات عشوائية: الحاسوب الكمومي .

تُساوي فئة ZPP تمامًا تقاطع فئتي RP و co-RP . ويُعتبر هذا غالبًا تعريفًا لـ ZPP . ولإثبات ذلك، تجدر الإشارة أولًا إلى أن كل مسألة تنتمي إلى كل من RP و co-RP لها خوارزمية لاس فيغاس كما يلي:

• لنفترض أن لدينا لغة L يتم التعرف عليها بواسطة كل من خوارزمية RP A وخوارزمية co-RP B (التي قد تكون مختلفة تمامًا).
• عند إدخال قيمة، قم بتشغيل البرنامج A على هذه القيمة لخطوة واحدة. إذا أعاد البرنامج القيمة YES، فالإجابة هي YES. وإلا، فقم بتشغيل البرنامج B على هذه القيمة لخطوة واحدة. إذا أعاد البرنامج القيمة NO، فالإجابة هي NO. إذا لم يحدث أي من الأمرين، فكرر هذه الخطوة.

لاحظ أنه لا يمكن إلا لآلة واحدة أن تعطي إجابة خاطئة، واحتمالية إعطاء تلك الآلة إجابة خاطئة في كل تكرار لا تتجاوز 50%. هذا يعني أن احتمالية الوصول إلى الجولة k تتناقص أُسّيًا مع k ، مما يدل على أن زمن التشغيل المتوقع متعدد الحدود. وهذا يُظهر أن RP intersect co-RP مُحتوى في ZPP .

لإثبات أن ZPP مُحتوى في RP intersect co-RP ، لنفترض أن لدينا خوارزمية لاس فيغاس C لحل مشكلة ما. يمكننا حينها بناء خوارزمية RP التالية :

• شغّل البرنامج C لمدة لا تقل عن ضعف وقت تشغيله المتوقع. إذا أعطى البرنامج إجابة، فاكتب تلك الإجابة. إذا لم يُعطِ أي إجابة قبل إيقافه، فاكتب "لا".

بحسب متباينة ماركوف ، فإن احتمال الحصول على إجابة قبل إيقاف العملية هو 1/2 على الأقل. هذا يعني أن احتمال إعطاء إجابة خاطئة في حالة "نعم"، بالتوقف وإعطاء "لا"، هو 1/2 على الأكثر، وهو ما يتوافق مع تعريف خوارزمية RP . خوارزمية co-RP مطابقة لها، باستثناء أنها تعطي "نعم" إذا "انتهت مهلة" العملية C.

يمكن اعتبار الفئات NP و RP و ZPP من حيث إثبات العضوية في مجموعة.

التعريف: جهاز التحقق V لمجموعة X هو آلة تورينج بحيث:

• إذا كان x ينتمي إلى X، فإنه يوجد سلسلة w بحيث تقبل V ( x , w )؛
• إذا لم يكن x موجودًا في X ، فإن V ( x , w ) يرفض جميع السلاسل w .

يمكن اعتبار السلسلة w بمثابة برهان على الانتماء. في حالة البراهين القصيرة (التي يكون طولها محدودًا بدالة متعددة الحدود بالنسبة لحجم المدخلات) والتي يمكن التحقق منها بكفاءة (حيث V هي آلة تورينغ حتمية تعمل في زمن متعدد الحدود)، تُسمى السلسلة w شاهدًا .

ملحوظات:

• التعريف غير متناظر للغاية. إثبات انتماء x إلى X هو سلسلة نصية واحدة. أما إثبات عدم انتماء x إلى X فهو مجموعة جميع السلاسل النصية، ولا تُعدّ أيٌّ منها دليلاً على الانتماء.
• لكل عنصر x في X، يجب أن يكون هناك شاهد على انتمائه إلى X.
• لا يشترط أن يكون الدليل دليلاً بالمعنى التقليدي. فإذا كانت V آلة تورينغ احتمالية يمكنها قبول x إذا كان x ينتمي إلى X، فإن الدليل هو سلسلة رميات العملة التي تؤدي بالآلة إلى قبول x (بشرط أن يكون لكل عنصر في X دليل، وألا تقبل الآلة أبدًا عنصرًا غير منتمٍ إلى X).
• المفهوم المشترك هو دليل على عدم الانتماء، أو الانتماء إلى المجموعة المكملة.

تُعدّ الفئات NP و RP و ZPP مجموعاتٍ لها شهودٌ على الانتماء. تتطلب الفئة NP وجود شهودٍ فقط، وقد يكونون نادرين جدًا. من بين 2^ ^{f (| x |)} سلسلةً ممكنة، حيث f دالةٌ متعددة الحدود، يكفي أن تُؤدي سلسلةٌ واحدةٌ فقط إلى قبول المُدقِّق (إذا كانت x تنتمي إلى X). إذا لم تكن x تنتمي إلى X، فلن تُؤدي أي سلسلةٍ إلى قبول المُدقِّق.

بالنسبة للفئتين RP و ZPP، من المرجح أن تكون أي سلسلة يتم اختيارها عشوائيًا بمثابة شاهد.

تحتوي الفئات المقابلة على دليل على عدم الانتماء. على وجه الخصوص، تُعرَّف co-RP بأنها فئة المجموعات التي إذا لم يكن العنصر x ينتمي إلى X، فمن المرجح أن تكون أي سلسلة مختارة عشوائيًا دليلًا على عدم الانتماء. أما ZPP فهي فئة المجموعات التي من المرجح أن تكون أي سلسلة عشوائية دليلًا على انتماء x إلى X، أو عدم انتمائه إليها، أيهما أسبق.

يسهل ربط هذا التعريف بتعريفات أخرى لـ RP و co-RP و ZPP . تتوافق آلة تورينغ الاحتمالية متعددة الحدود V* _w ( x ) مع آلة تورينغ الحتمية متعددة الحدود V ( x , w ) باستبدال الشريط العشوائي لـ V* بشريط إدخال ثانٍ لـ V مكتوب عليه تسلسل رميات العملة. باختيار الشاهد كسلسلة عشوائية، يكون المُدقِّق آلة تورينغ احتمالية متعددة الحدود، حيث يكون احتمال قبول x عندما يكون x في X كبيرًا (أكبر من 1/2، على سبيل المثال)، ولكنه يساوي صفرًا إذا كان x ∉ X (بالنسبة لـ RP )؛ ويكون احتمال رفض x عندما لا يكون x في X كبيرًا ولكنه يساوي صفرًا إذا كان x ∈ X (بالنسبة لـ co-RP )؛ ويكون احتمال قبول أو رفض x بشكل صحيح كعضو في X كبيرًا، ولكنه يساوي صفرًا في حالة قبول أو رفض x بشكل خاطئ (بالنسبة لـ ZPP ).

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

يجب التمييز بين ZPP و BPP . لا تتطلب فئة BPP أدلة، مع أن الأدلة كافية (لذا فإن BPP تشمل RP و co-RP و ZPP ). في لغة BPP، تقبل الدالة V(x,w) أغلبية (واضحة) من السلاسل w إذا كانت x تنتمي إلى X، وترفضها في المقابل إذا لم تكن x تنتمي إلى X. لا يشترط أن تكون أي سلسلة w قاطعة، وبالتالي لا يمكن اعتبارها عمومًا براهين أو أدلة.

ZPP مغلق تحت المكمل، أي ZPP = co- ZPP (هذا يتبع من ZPP = RP ∩ co- RP ).

قيمة ZPP منخفضة في حد ذاتها، مما يعني أن جهاز ZPP الذي يمتلك القدرة على حل مسائل ZPP فورًا (جهاز ZPP أوراكل) ليس أقوى من الجهاز الذي لا يمتلك هذه القدرة الإضافية. بالرموز ، ZPP = ^ZPP .

ZPP ^{NP BPP} = ZPP ^NP .

يحتوي ZPP NP على ^{NP BPP} .

بما أن ZPP = RP ∩ coRP ، فمن الواضح أن ZPP موجود في كل من RP و coRP .

يتم تضمين الفئة P في ZPP ، وقد افترض بعض علماء الكمبيوتر أن P = ZPP ، أي أن كل خوارزمية لاس فيغاس لها مكافئ حتمي متعدد الحدود.

يوجد وسيط منطقي بالنسبة له يكون ZPP = EXPTIME . ^{[ 1 ]} إن إثبات أن ZPP = EXPTIME يستلزم أن P ≠ ZPP ، لأن P ≠ EXPTIME (انظر نظرية التسلسل الهرمي الزمني ).

• بي بي بي
• آر بي

• حديقة التعقيد : فئة ZPP