بي بي (تعقيد حسابي)
في البداية، في نظرية التعقيد الحسابي القسم PP هو قسم لالات تيورنج الاحتمالية التي تخطأ على كل المدخلات باحتمال . وفيما يلي تفاصيل أوسع عن ذلك.
كذلك، الكلمة PP هي اختصار للكلمتين probabilistic polynomial , قسم التعقيد هذا عرفه غيل عام 1977.
علاقته مع أقسام أخرى
كذلك، MA⊆PP , فلتكن لذا يوجد كثير حدود (p(n , ويوجد آلة تيورنج قطعية كثيرة الحدود بحيث يتحقق:
- لذا حسب التعريف L تتبع PP .
- BQP⊆PP
- PPBQP=PP
- PH⊆PPP=P#P هذه النتيجة تُسمى مبرهنة تودا
وفي هذا السياق، coNP⊆PP , بما أنّ PP منغلق للمكمل وبما أنَّ NP مجموعة جزئية ل-PP لذا كذلك coNP مجموعة جزئية ل- PP.
نأخذ كثير حدود p1 ونستطيع أن نصغر الخطأ كما نريد. لذا:
وعلى صعيد آخر، في حين أنَّ الاحتمال الموحد مأخوذ في r∈ {0,1}p1 ، فلننظر إلى الزوج ، ويتحقق التالي:
من جانب آخر، BPP⊆PP وهذا لأن الخطأ في الآلات تيورنج التابعة للقسم PP أكبر منه في BPP لذا فان BPP هي مجموعة جزئية ل- PP .
وفي هذا الصدد، NP⊆PP , لبيان هذا علينا أن نبين أنَّ مسألة الاكتفاء SAT تابعة للقسم PP ، لذا علينا أن نبني خوارزمية التي تخطأ على كل المدخلات باحتمال أقل من النصف. الخوارزمية جدا بسيطة: لكل متغير اختر بشكل عشوائي 0 أو 1، افحص إذا ما الصيغة مكتفية إذا كانت مكتفية الجواب «نعم» خلاف هذا نختار «نعم» أو «لا» بشكل عشوائي مُوحد. نلاحظ أنه إذا كانت الصيغة غير قابلة للاكتفاء الجواب «نعم» باحتمال 1/2 . لذا هذه الخوارزمية تحقق المطلوب. وبما أن مسألة الاكتفاء NP كاملة أي يمكن اختصار كل مسألة في NP لمسألة الاكتفاء لذا فإن كل مسألة في NP كذلك تتبع PP .
مسائل كاملة
في هذا الإطار، بخلاف أقسام احتمالية أخرى لهذا القسم يوجد مسائل كاملة، ونعني بالمسائل الكاملة أنها تابعة للقسم PP ، كما أن هذه المسائل يمكن اختصار أي مسألة في PP لهذه المسألة بواسطة اختصارات متعددة الحدود، أحد الأمثلة المهمة هي MAJSAT أي مسألة الاكتفاء مع أغلبية (أكثر من النصف) التعويضات في الصيغة، التي هي صيغة على شكل CNF ، قيمتها هي «صحيح» (أو 1).
قسم تعقيد
- نظرية التعقيد الحسابي.
- مسألة P=NP
- خوارزمية
حيث أنَّ
من جهة ثانية، تعريف آخر لهذا القسم هو أنه قسم الآلات تيورنج غير قطعية حيث أنَّ أغلبية (أكثر من النصف) مسارات الحساب موافقة (أي جوابها «نعم»), أي:
تعريف
إذا يوجد آلة تيورنج احتمالية، M ، حيث يتحقق:
TC0 ⊂PP
- (k , ∃ L∈{0,1}* : L∈PP ∧ L∉SIZE(n^k ∀ هذه النتيجة نابعة من مبرهنة كارب ليبتون.
- PostBQP=PP ,
- PQP=PP ,
- انظر كذلك
من جانب آخر، PP⊆ PSPACE ، حتى نبين هذا علينا أن نبرهن أنَّ MAJSAT تتبع القسم PSPACE وهذا سهل للغاية بما أننا يمكننا أن نحاكي كل مسارات الحساب في آلة تيورنج غير قطعية كثيرة الحدود بواسطة مساحة متعددة الحدود.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟