PP (التعقيد)

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 18 صور
الموسوعة الحرة
خوارزمية PP
إجابة
تم إنتاجه
الإجابة الصحيحة
نعملا
نعم> 1/2< 1/2
لا< 1/2> 1/2
مخطط فئات التعقيد العشوائي
تُقارن PP بفئات التعقيد الاحتمالي الأخرى ( ZPP ، RP ، co-RP، BPP ، BQP )، التي تُعمم P ضمن PSPACE . من غير المعروف ما إذا كانت أي من هذه الإضافات صارمة.

في نظرية التعقيد ، تُعرف PP أو PPT بأنها فئة مسائل القرار التي يمكن حلها بواسطة آلة تورينغ الاحتمالية في وقت متعدد الحدود ، مع احتمال خطأ أقل من 1/2 لجميع الحالات. يشير الاختصار PP إلى الوقت متعدد الحدود الاحتمالي. وقد عرّف جيل هذه الفئة من التعقيد عام 1977. [ 1 ]

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

تُصنف آلات تورينغ ذات الوقت الزمني متعدد الحدود والاحتمالية ضمن فئة PPT ، وهي اختصار لآلات الوقت الزمني متعدد الحدود الاحتمالية. [ 2 ] لا يشترط هذا التصنيف لآلات تورينغ وجود احتمال خطأ محدود. لذا، فإن PP هي فئة التعقيد التي تضم جميع المسائل التي يمكن حلها بواسطة آلة PPT باحتمال خطأ أقل من 1/2.

يُمكن تعريف مشكلة PP بشكل بديل بأنها مجموعة المشكلات التي يُمكن حلها بواسطة آلة تورينغ غير حتمية في وقت متعدد الحدود، حيث يكون شرط القبول هو قبول أغلبية (أكثر من النصف) مسارات الحساب. ولهذا السبب، اقترح بعض الباحثين تسميتها بالمشكلة الرئيسية ( Majority-P) . [ 3 ]

تعريف

تكون اللغة L في فئة PP إذا وفقط إذا وُجدت آلة تورينغ احتمالية M ، بحيث

  • يتم تشغيل M في وقت متعدد الحدود على جميع المدخلات
  • لكل قيمة x في L ، تُخرج M القيمة 1 باحتمالية لا تقل عن 1/2
  • بالنسبة لجميع قيم x غير الموجودة في L ، فإن M تُخرج 1 باحتمالية أقل من 1/2.

بدلاً من ذلك، يمكن تعريف PP باستخدام آلات تورينغ الحتمية فقط. تكون اللغة L في PP إذا وفقط إذا وُجدت متعددة حدود p وآلة تورينغ حتمية M ، بحيث

  • يتم تشغيل M في وقت متعدد الحدود على جميع المدخلات
  • لكل x في L ، فإن نسبة السلاسل y ذات الطول p (| x |) التي تحقق M ( x , y ) = 1 لا تقل عن 1/2
  • بالنسبة لجميع x غير الموجودة في L ، فإن نسبة السلاسل y ذات الطول p (| x |) التي تحقق M ( x , y ) = 1 أقل من 1/2.

في هذا التعريف، تتوافق السلسلة y مع ناتج رميات العملة العشوائية التي كانت ستجريها آلة تورينج الاحتمالية.

في كلا التعريفين، يمكن تغيير "أقل من" إلى "أقل من أو يساوي" (انظر أدناه)، ويمكن استبدال الحد الأدنى 1/2 بأي عدد نسبي ثابت في (0،1)، دون تغيير الفئة.

PP مقابل BPP

تُعدّ BPP مجموعة فرعية من PP ؛ ويمكن اعتبارها المجموعة الفرعية التي توجد لها خوارزميات احتمالية فعّالة. يكمن الاختلاف في احتمال الخطأ المسموح به: في BPP ، يجب أن تُعطي الخوارزمية الإجابة الصحيحة (نعم أو لا) باحتمال يتجاوز قيمة ثابتة c > 1/2، مثل 2/3 أو 501/1000. في هذه الحالة، يُمكننا تشغيل الخوارزمية عدة مرات، ثمّ نعتمد على تصويت الأغلبية لتحقيق أي احتمال صحة مطلوب أقل من 1، باستخدام حد تشيرنوف . يزداد عدد مرات التكرار هذه كلما اقتربت قيمة c من 1/2، ولكنه لا يعتمد على حجم المُدخلات n .

وبشكل أعم، إذا كان بإمكان c أن يعتمد على حجم المدخلاتن{\displaystyle n}متعدد الحدود، كماج=يا(ن-ك){\displaystyle c=O(n^{-k})}ثم يمكننا إعادة تشغيل الخوارزمية لـيا(ن2ك){\displaystyle O(n^{2k})}ثم يتم اختيار أغلبية الأصوات. وبحسب متباينة هوفدينغ ، نحصل بذلك على خوارزمية BPP .

الأمر المهم هو أنه لا يُسمح لهذا الثابت c بالاعتماد على المُدخلات. من ناحية أخرى، يُسمح لخوارزمية PP بالقيام بشيء مثل ما يلي:

  • في حالة YES، قم بإخراج YES باحتمالية 1/2  +  1/2 n ، حيث n هو طول المدخلات.
  • في حالة "لا"، قم بإخراج "نعم" باحتمالية 1/2  -  1/2 ن .

نظرًا لتقارب هذين الاحتمالين بشكلٍ أُسّي ، فإنه حتى لو أجرينا العملية لعددٍ كثير الحدود من المرات، يصعب جدًا تحديد ما إذا كنا نتعامل مع حالة "نعم" أو حالة "لا". إن محاولة الوصول إلى مستوى احتمال ثابت مرغوب فيه باستخدام التصويت بالأغلبية وحد تشيرنوف تتطلب عددًا من التكرارات يتناسب أُسّيًا مع n .

مقارنة بفئات التعقيد الأخرى

يشمل PP كلاً من BPP ، حيث أن الخوارزميات الاحتمالية الموصوفة في تعريف BPP تشكل مجموعة فرعية من تلك الموجودة في تعريف PP .

يشمل PP أيضًا NP . ولإثبات ذلك، نُبين أن مسألة الإرضاء الكاملة من فئة NP تنتمي إلى PP . لنفترض خوارزمية احتمالية، عند إعطائها صيغة F ( x1 , x2 , ..., xn ) ، تختار تعيينًا x1 , x2 , ... , xn عشوائيًا وبشكل منتظم. ثم تتحقق الخوارزمية مما إذا كان التعيين يجعل الصيغة F صحيحة. إذا كانت كذلك، فإنها تُخرج " نعم " . وإلا، فإنها تُخرج " نعم" باحتمالية      12-12ن+1{\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}}ولا باحتمال12+12ن+1{\displaystyle {\frac {1}{2}}+{\frac {1}{2^{n+1}}}}.

إذا كانت الصيغة غير قابلة للتحقيق، فستُخرج الخوارزمية دائمًا القيمة "نعم" باحتمالية معينة.12-12ن+1<12{\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}<{\frac {1}{2}}}إذا وُجدت عملية تعيين مُرضية، فسيتم إخراج "نعم" باحتمالية لا تقل عن (12-12ن+1)⋅(1-12ن)+1⋅12ن=12+122ن+1>12\displaystyle \left({\frac {1}{2}}-{\frac {1}{2^{n+1}}}\right)\cdot \left(1-{\frac {1}{2^{n}}}\right)+1\cdot {\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{2^{2n+1}}}>{\frac {1}{2}}} (يُساوي 1/2 بالضبط إذا اختارت الخوارزمية مهمة غير مُرضية، و1 إذا اختارت مهمة مُرضية، بمتوسط ​​يزيد عن 1/2). بالتالي، تُدرج هذه الخوارزمية إمكانية الإرضاء ضمن PP . ولأن SAT مسألة NP-كاملة، وبما أنه يُمكننا إضافة أي اختزال حتمي متعدد الحدود إلى خوارزمية PP ، فإن NP مُضمنة في PP . ولأن PP مُغلقة تحت المُتمِّم، فإنها تشمل أيضًا co-NP .

علاوة على ذلك، يشمل PP MA ، [ 4 ] الذي يشمل الإدراجين السابقين.

يشمل PP أيضًا BQP ، وهي فئة مسائل القرار التي يمكن حلها بواسطة الحواسيب الكمومية الفعالة ذات الوقت متعدد الحدود . في الواقع، يكون BQP منخفضًا بالنسبة لـ PP ، مما يعني أن جهاز PP لا يستفيد من قدرته على حل مسائل BQP بشكل فوري. فئة الوقت متعدد الحدود على الحواسيب الكمومية مع الاختيار اللاحق ، PostBQP ، تساوي PP [ 5 ] (انظر #PostBQP أدناه).

علاوة على ذلك، يشمل PP كلاً من QMA ، الذي يتضمن تضمينات MA و BQP .

يمكن لآلة تورينغ ذات زمن متعدد الحدود، المزودة بـ PP oracle ( PP ) ، حل جميع المسائل في PH ، أي التسلسل الهرمي متعدد الحدود بأكمله . وقد أثبت سينوسوكي تودا هذه النتيجة عام 1989، وتُعرف باسم نظرية تودا . وهذا دليل على صعوبة حل المسائل في PP . وتُعتبر الفئة #P صعبةً بنفس القدر تقريبًا، لأن P #P = PP ، وبالتالي فإن P #P تشمل PH أيضًا. [ 6 ]

يشمل PP بشكل صارم TC 0 المنتظم، وهو فئة من الدوائر المنطقية ذات العمق الثابت وعدد غير محدود من المدخلات مع بوابات الأغلبية المنتظمة (التي يتم إنشاؤها بواسطة خوارزمية زمنية متعددة الحدود). [ 7 ]

تُدرج PP في PSPACE . ويمكن إثبات ذلك بسهولة من خلال عرض خوارزمية فضاء متعدد الحدود لـ MAJSAT ، الموضحة أدناه؛ ببساطة جرب جميع التعيينات واحسب عدد التعيينات المُرضية.

لا يتم تضمين PP في SIZE (n k ) لأي k، وفقًا لنظرية كانان .

مسائل كاملة وخصائص أخرى

على عكس BPP ، فإن PP هي فئة نحوية وليست دلالية. أي آلة احتمالية تعمل في زمن متعدد الحدود تتعرف على لغة ما في PP . في المقابل، عند إعطاء وصف لآلة احتمالية تعمل في زمن متعدد الحدود، فإنه من غير الممكن عمومًا تحديد ما إذا كانت تتعرف على لغة في BPP .

تتضمن مسائل PP مسائل كاملة طبيعية، على سبيل المثال، MAJSAT . [ 1 ] MAJSAT هي مسألة قرار حيث تُعطى صيغة منطقية F. يجب أن تكون الإجابة نعم إذا كان أكثر من نصف جميع التعيينات x1، x2 ، ... ، xn تجعل F صحيحة، ولا فيما عدا ذلك.   

إثبات أن PP مغلق تحت المتمم

لتكن L لغة في PP .لج{\displaystyle L^{c}}لنرمز إلى متمم L. بحسب تعريف PP، توجد خوارزمية احتمالية A ذات زمن متعدد الحدود تتمتع بالخاصية التالية:

x∈ل⇒برو[أ يقبل x]>12وx∉ل⇒برو[أ يقبل x]≤12.{\displaystyle x\in L\Rightarrow \Pr[A{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L\Rightarrow \Pr[A{\text{ accepts }}x]\leq {\frac {1}{2}}.}

نزعم أنه دون فقدان للعمومية ، فإن المتباينة الأخيرة تكون دائمًا صارمة؛ ويمكن استنتاج النظرية من هذا الزعم: ليكنأج{\displaystyle A^{c}}يشير إلى الآلة التي هي نفسها الآلة A باستثناء أنأج{\displaystyle A^{c}}يقبل عندما يرفض أ ، والعكس صحيح. ثم

x∈لج⇒برو[أج يقبل x]>12وx∉لج⇒برو[أج يقبل x]<12،{\displaystyle x\in L^{c}\Rightarrow \Pr[A^{c}{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L^{c}\Rightarrow \Pr[A^{c}{\text{ accepts }}x]<{\frac {1}{2}},}

مما يعني أنلج{\displaystyle L^{c}}موجود في PP .

والآن نبرر فرضيتنا دون الإخلال بعمومية المسألة. ليكنو(|x|){\displaystyle f(|x|)}ليكن الحد الأعلى متعدد الحدود لوقت تشغيل A على المدخل x . وبالتالي، فإن A يستغرق على الأكثرو(|x|){\displaystyle f(|x|)}يتم إجراء رميات عشوائية للعملة المعدنية أثناء تنفيذها. على وجه الخصوص، احتمال القبول هو مضاعف صحيح لـ2-و(|x|){\displaystyle 2^{-f(|x|)}}ولدينا:

x∈ل⇒برو[أ يقبل x]≥12+12و(|x|).{\displaystyle x\in L\Rightarrow \Pr[A{\text{ accepts }}x]\geq {\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}.}

عرّف الآلة A ′ كما يلي: عند إدخال x ، تقوم A ′ بتشغيل A كبرنامج فرعي، وترفض إذا كانت A سترفض؛ وإلا، إذا كانت A ستقبل، فإن A ′ تنقلب.و(|x|)+1{\displaystyle f(|x|)+1}يتم رفض العملات المعدنية إذا كانت جميعها تحمل صورة الوجه، ويتم قبولها في غير ذلك.

x∉ل⇒برو[أ′ يقبل x]≤12⋅(1-12و(|x|)+1)<12{\displaystyle x\not \in L\Rightarrow \Pr[A'{\text{ accepts }}x]\leq {\frac {1}{2}}\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)<{\frac {1}{2}}}

و

x∈ل⇒برو[أ′ يقبل x]≥(12+12و(|x|))⋅(1-12و(|x|)+1)>12.{\displaystyle x\in L\Rightarrow \Pr[A'{\text{ accepts }}x]\geq \left({\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}\right)\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)>{\frac {1}{2}}.}

وهذا يبرر الافتراض (لأن A ′ لا تزال خوارزمية احتمالية ذات وقت متعدد الحدود) ويكمل البرهان.

أثبت ديفيد روسو في أطروحته للدكتوراه عام 1985 [ 8 ] أن مجموعة PP مغلقة تحت عملية الفرق المتناظر . وظلت مسألة ما إذا كانت PP مغلقة تحت عمليتي الاتحاد والتقاطع مفتوحة لمدة 14 عامًا ؛ وقد حُسمت هذه المسألة بالإيجاب على يد بيجل، ورينغولد، وسبيل مان. [ 9 ] وقدّم لي [ 10 ] وآرونسون براهين بديلة لاحقًا (انظر #PostBQP أدناه).

فئات التعقيد المكافئة الأخرى

PostBQP

تُعرف فئة التعقيد الكمومي BQP بأنها فئة المسائل القابلة للحل في وقت متعدد الحدود على آلة تورينج الكمومية . بإضافة الاختيار اللاحق ، نحصل على فئة أكبر تُسمى PostBQP . ببساطة، يمنح الاختيار اللاحق الحاسوب القدرة التالية: عندما يكون لحدث ما (مثل قياس كيوبت في حالة معينة) احتمال غير صفري، يُسمح بافتراض حدوثه. [ 11 ] أثبت سكوت آرونسون في عام 2004 أن PostBQP تساوي PP . [ 5 ] [ 12 ] هذه الصياغة الجديدة لـ PP تُسهّل إثبات بعض النتائج، مثل أن PP مغلقة تحت التقاطع (وبالتالي، تحت الاتحاد)، وأن BQP منخفضة لـ PP ، وأن QMA مُضمنة في PP .

برنامج التأهيل المهني

تُعادل PP أيضًا فئة أخرى من فئات التعقيد الكمومي تُعرف باسم PQP ، وهي نظير BQP في حالة الخطأ غير المحدود. تُشير هذه الفئة إلى مجموعة مسائل القرار التي يُمكن حلها بواسطة حاسوب كمومي في وقت متعدد الحدود، باحتمالية خطأ أقل من 1/2 لجميع الحالات. حتى لو تم استخلاص جميع السعات المستخدمة في حساب PQP من أعداد جبرية، فإن PQP لا تزال تتطابق مع PP . [ 13 ]

ملحوظات

  1. 1 2 جيل، جون (1977). "التعقيد الحسابي لآلات تورينج الاحتمالية". مجلة SIAM للحوسبة . 6 (4): 675-695 . doi : 10.1137/0206049 .
  2. ↑ ليندل، يهودا؛ كاتز، جوناثان (2015). مقدمة في التشفير الحديث ( الطبعة الثانية). تشابمان آند هول/سي آر سي. ص 46. ISBN   978-1-4665-7027-6.
  3. ↑ لانس فورتناو. التعقيد الحسابي: الأربعاء، 4 سبتمبر 2002: درس التعقيد لهذا الأسبوع: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
  4. ↑ "إن كيه فيريشاجين، "حول قوة PP"تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 29-12-2014 . تم الاطلاع عليه بتاريخ 17-08-2011 .
  5. 1 2 آرونسون، سكوت (2005). "الحوسبة الكمومية، والاختيار اللاحق، والوقت متعدد الحدود الاحتمالي". وقائع الجمعية الملكية أ . 461 (2063): 3473-3482 . arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 . 
  6. ↑ تودا، سينوسوكي (1991). "صعوبة البرمجة متعددة الحدود تضاهي صعوبة التسلسل الهرمي ذي الوقت متعدد الحدود". مجلة SIAM للحوسبة . 20 (5): 865-877 . doi : 10.1137/0220053 . MR 1115655 . 
  7. ↑ أليندر 1996، كما ورد في بورتشيك 1999
  8. ↑ ديفيد روسو (1985). الخصائص الهيكلية لفئات التعقيد (أطروحة دكتوراه). جامعة كاليفورنيا، سانتا باربرا.
  9. ↑ R. Beigel, N. Reingold, and DA Spielman, “ PP is closed under intersection “, Proceedings of ACM Symposium on Theory of Computing 1991 , pp. 1–9, 1991.
  10. ↑ ليد لي (1993). حول دوال العد (أطروحة دكتوراه). جامعة شيكاغو.
  11. ↑ آرونسون، سكوت. "القوة المذهلة للاختيار اللاحق" . تم الاسترجاع في 27-07-2009 .
  12. ↑ آرونسون، سكوت (11 يناير 2004). "درس التعقيد لهذا الأسبوع: PP" . مدونة التعقيد الحسابي . تم الاطلاع عليه بتاريخ 2 مايو 2008 .
  13. ↑ ياماكامي، تومويوكي (1999). "تحليل الدوال الكمومية". المجلة الدولية لأسس علوم الحاسوب 14 (5): 815-852 . arXiv : quant-ph/9909012 . Bibcode : 1999quant.ph..9012Y . doi : 10.1142/S0129054103002047 . S2CID 3265603 . 

مراجع

  • باباديميتريو، سي. (1994). "الفصل 11". التعقيد الحسابي . أديسون-ويسلي..
  • أليندر، إي. (1996). "ملاحظة حول الحدود الدنيا الموحدة للدوائر في التسلسل الهرمي للعد". وقائع المؤتمر الدولي الثاني للحوسبة والتوافقية (COCOON) . سلسلة محاضرات في علوم الحاسوب. المجلد  1090. دار نشر سبرينغر. الصفحات 127-135 . .
  • بورتشيك، هانز-يورغ؛ فولمر، هيريبيرت (1998). "محددات ليندستروم وقابلية تعريف لغة الأوراق". المجلة الدولية لأسس علوم الحاسوب 9 ( 3): 277-294 . doi : 10.1142/S0129054198000180 . ECCC TR96-005 .