بي بي (تعقيد حسابي)

في نظرية التعقيد الحسابي القسم PP هو قسم لالات تيورنج الاحتمالية التي تخطأ على كل المدخلات باحتمال .

الكلمة PP هي اختصار للكلمتين probabilistic polynomial , قسم التعقيد هذا عرفه غيل عام 1977.[1]

تعريف
  • إذا يوجد آلة تيورنج احتمالية، M ، حيث يتحقق:

حيث أنَّ

  • تعريف آخر لهذا القسم هو أنه قسم الآلات تيورنج غير قطعية حيث أنَّ أغلبية (أكثر من النصف) مسارات الحساب موافقة (أي جوابها «نعم»), أي:

مسائل كاملة

بخلاف أقسام احتمالية أخرى لهذا القسم يوجد مسائل كاملة، ونعني بالمسائل الكاملة أنها تابعة للقسم PP ، كما أن هذه المسائل يمكن اختصار أي مسألة في PP لهذه المسألة بواسطة اختصارات متعددة الحدود، أحد الأمثلة المهمة هي MAJSAT أي مسألة الاكتفاء مع أغلبية (أكثر من النصف) التعويضات في الصيغة، التي هي صيغة على شكل CNF ، قيمتها هي «صحيح» (أو 1).

علاقته مع أقسام أخرى
  • BPP⊆PP وهذا لأن الخطأ في الآلات تيورنج التابعة للقسم PP أكبر منه في BPP لذا فان BPP هي مجموعة جزئية ل- PP .
  • NP⊆PP , لبيان هذا علينا أن نبين أنَّ مسألة الاكتفاء SAT تابعة للقسم PP ، لذا علينا أن نبني خوارزمية التي تخطأ على كل المدخلات باحتمال أقل من النصف. الخوارزمية جدا بسيطة: لكل متغير اختر بشكل عشوائي 0 أو 1، افحص إذا ما الصيغة مكتفية إذا كانت مكتفية الجواب «نعم» خلاف هذا نختار «نعم» أو «لا» بشكل عشوائي مُوحد. نلاحظ أنه إذا كانت الصيغة غير قابلة للاكتفاء الجواب «نعم» باحتمال 1/2 . لذا هذه الخوارزمية تحقق المطلوب. وبما أن مسألة الاكتفاء NP كاملة أي يمكن اختصار كل مسألة في NP لمسألة الاكتفاء لذا فإن كل مسألة في NP أيضاً تتبع PP .
  • coNP⊆PP , بما أنّ PP منغلق للمكمل وبما أنَّ NP مجموعة جزئية ل-PP لذا أيضاً coNP مجموعة جزئية ل- PP.
  • MA⊆PP , فلتكن لذا يوجد كثير حدود (p(n , ويوجد آلة تيورنج قطعية كثيرة الحدود بحيث يتحقق:

نأخذ كثير حدود p1 ونستطيع أن نصغر الخطأ كما نريد. لذا:

في حين أنَّ الاحتمال الموحد مأخوذ في r∈ {0,1}p1 ، فلننظر إلى الزوج ، ويتحقق التالي:


لذا حسب التعريف L تتبع PP .

  • BQP⊆PP[2]
  • PPBQP=PP
  • PH⊆PPP=P#P هذه النتيجة تُسمى مبرهنة تودا[3]
  • TC0 ⊂PP [4]
  • PP⊆ PSPACE ، حتى نبين هذا علينا أن نبرهن أنَّ MAJSAT تتبع القسم PSPACE وهذا سهل للغاية بما أننا يمكننا أن نحاكي كل مسارات الحساب في آلة تيورنج غير قطعية كثيرة الحدود بواسطة مساحة متعددة الحدود.
  • (k , ∃ L∈{0,1}* : L∈PP ∧ L∉SIZE(n^k ∀ هذه النتيجة نابعة من مبرهنة كارب ليبتون.[5]
  • PostBQP=PP ,
  • PQP=PP ,

انظر أيضا

مراجع
  1. J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.
  2. L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.
  3. S. TODA: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991.
  4. Allender, E. (1996), A note on uniform circuit lower bounds for the counting hierarchy, “Proceedings 2nd International Computing and Combinatorics Conference (COCOON)”, Springer Lecture Notes in Computer Science 1090: 127–135
  5. N. V. Vinodchandran, A note on the circuit complexity of PP نسخة محفوظة 25 أبريل 2012 على موقع واي باك مشين.


  • بوابة رياضيات
  • بوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.