ZPP (تعقيد حسابي)
قبل الخوض في التفاصيل، في نظرية التعقيد الحسابي القسم هو قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية بوقت حدودي مع إمكانية الفشل في الاتيان بجواب، كذلك تعريف هذا القسم بأنه قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية التي لا تخطئ أبدًا بحيث أن وقتها المتوقع (expected running time) هو حدودي أي أي لو أن الخوارزمية ترمي قطع نقدية عشوائية خلال وقت عملها فإنَّ جوابها صحيح دائما ولكن معدل وقت عملها لكل مُدخل طوله هو (p(n ، حيث أنَّ (p(n هو كثير حدود، القول الاخير يعني انه بشكل عام وقت عمل الخوارزمية هو كثير حدود ولكن يمكن أن يكون هناك مُدخلات بحيث أن وقت عمل الخوارزمية أكثر من حدودي. التعريفان متكافئان. وفيما يلي تفاصيل أوسع عن ذلك.
حدسيات
ومن ناحية أخرى، هل ZPP=NP ? إذا كان الجواب «لا» حينها NP لا يساوي P. خلاف هذا تظل مسألة NP مقابل P حدسية.
ومن جهة أخرى، كما هو معلوم لعل حل حدسية NP-P هي الأشهر ولكن هنالك عدة حدسيات لم تُحل مثل:
إضافةً إلى ذلك، هل ZPP=BPP=EXP ? إذا كان الجواب «نعم» حينها P لا يساوي NP خلاف هذا المسألة NP مقابل P تظل حدسية
وفي هذا السياق، هل ZPP=P ? وهذا السؤال كذلك ما زال حدسية ولكن العلماء يظنون ان الجواب نعم وعلى خلاف الأسئلة التي طرحت آنفا فان الإجابة عن السؤال هذا قد لا تُحدث تطورا في العلاقة بين NP و- P .
انظر كذلك
قسم تعقيد
- نظرية التعقيد الحسابي.
- مسألة P=NP
- خوارزمية
نعرف
من جانب آخر، تعريف آخر هو: أي انَّ ZPP هو قسم المسائل التي يوجد لها آلة تيورنج احتمالية بحيث أنَّ احتمال ان تخطأ الآلة على مُدخلات تابعة للمسألة (أي جوابها الصحيح «نعم») هو على الأكثر 1/2 وكذلك يوجد آلة أخرى تحل مسألة التقرير لهذه المسألة وتخطأ على مُدخلات ليست تابعة للمسألة (أي جوابها الصحيح «لا») باحتمال على الأكثر 1/2 .
- إذا يوجد آلة تيورنج احتمالية كثيرة الحدود،A, بحيث أنه لكل :
- بحيث أن:
- والرمز معناه ان الخوارزمية لم تنجح في الاتيان باجابة صحيحة.
تعريف
علاوةً على ذلك، القسم يحوي كل المسائل أو اللغات،L, والتي يوجد آلة تيورنج احتمالية حيث أن وقتها المُتوقع هو وهذه الآلة لا تخطئ أي:
علاقتها بأقسام خرى
وفي هذا الصدد، ZPP يحوي P وذلك لان لكل مسألة في القسم P يمكن محاكاة الآلة الحتمية التي تحل مسألة القرار بواسطة آلة تيورنج احتمالية.
ZPP مَحوي ب- .
ZPP مَحوي ب- BPP وذلك لان .
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟