مكتملة P

في نظرية التعقيد الحسابي ، تكون مشكلة القرار كاملة من النوع P ( كاملة لفئة التعقيد P ) إذا كانت موجودة في P ويمكن اختزال كل مشكلة في P إليها عن طريق اختزال مناسب.

إن مفهوم مشاكل القرار الكاملة من النوع P مفيد في تحليل المشاكل التي يصعب موازاتها بشكل فعال والمشاكل التي يصعب حلها في مساحة محدودة، وتحديداً عند النظر في مفاهيم أقوى للاختزال من الاختزال متعدد الأوقات.

يختلف نوع الاختزال المستخدم وقد يؤثر على مجموعة المسائل المحددة. عمومًا، تُستخدم اختزالات أكثر صرامة من اختزالات الوقت متعدد الحدود، لأن جميع اللغات في P (باستثناء اللغة الفارغة ولغة جميع السلاسل النصية) هي P- كاملة في ظل اختزالات الوقت متعدد الحدود. إذا استخدمنا اختزالات NC ، أي الاختزالات التي يمكن تشغيلها في وقت متعدد اللوغاريتمات على حاسوب متوازٍ بعدد متعدد الحدود من المعالجات، فإن جميع المسائل P- الكاملة تقع خارج NC ، وبالتالي لا يمكن موازاتها بفعالية، وذلك بافتراض غير مثبت أن NC  ≠ P. إذا استخدمنا اختزال المساحة اللوغاريتمية الأقوى ، يظل هذا صحيحًا، ولكننا نكتشف أيضًا أن جميع المسائل P- الكاملة تقع خارج L بافتراض أضعف غير مثبت أن L ≠ P. في هذه الحالة الأخيرة، قد تكون مجموعة المسائل P- الكاملة أصغر.   

تحتوي الفئة P ، التي تُعتبر عادةً جميع المسائل "القابلة للحل" على حاسوب تسلسلي، على الفئة NC ، التي تتكون من المسائل التي يمكن حلها بكفاءة على حاسوب متوازي. وذلك لأن الحواسيب المتوازية يُمكن محاكاتها على جهاز تسلسلي. ولا يُعرف ما إذا كانت NC  تساوي P. بعبارة أخرى، لا يُعرف ما إذا كانت هناك أي مسائل قابلة للحل تسلسلية بطبيعتها. وكما يُشتبه على نطاق واسع في أن P لا تساوي NP ، يُشتبه أيضاً على نطاق واسع في أن NC لا تساوي P. 

وبالمثل، تحتوي الفئة L على جميع المسائل التي يمكن حلها بواسطة حاسوب تسلسلي في مساحة لوغاريتمية. تعمل هذه الحواسيب في وقت متعدد الحدود لأنها لا تملك إلا عددًا متعدد الحدود من التكوينات المختلفة. ويُشتبه في أن L  ≠ P ؛ أي أن بعض المسائل التي يمكن حلها في وقت متعدد الحدود تتطلب أيضًا مساحة أكبر من لوغاريتمية. 

على غرار استخدام مسائل NP-complete لتحليل مسألة P  = NP ، تُستخدم مسائل P -complete، التي تُعتبر مسائل "غير قابلة للتوازي على الأرجح" أو "متسلسلة بطبيعتها على الأرجح"، بطريقة مماثلة لدراسة مسألة NC = P. إن إيجاد طريقة فعّالة لموازاة حل مسألة P -complete سيُثبت أن NC = P. ويمكن اعتبارها أيضًا "مسائل تتطلب مساحة فائقة اللوغاريتم"؛ فحلٌّ في مساحة لوغاريتمية لمسألة P - complete (باستخدام التعريف القائم على اختزالات المساحة اللوغاريتمية) سيُشير إلى أن L = P.       

المنطق الكامن وراء ذلك مماثل للمنطق القائل بأن حلًا زمنيًا متعدد الحدود لمسألة NP- كاملة سيثبت أن P  = NP : إذا كان لدينا اختزال NC من أي مسألة في P إلى مسألة A ، وحل NC لـ A ، فإن NC = P. وبالمثل، إذا كان لدينا اختزال لوغاريتمي من أي مسألة في P إلى مسألة A ، وحل لوغاريتمي لـ A ، فإن L = P.     

توجد العديد من عمليات الاختزال المتعددة-الواحدية المختلفة المستخدمة عند تعريف اكتمال P ، بدرجات متفاوتة من القوة. ^{[ 1 ] : القسم 3.3}

في أدنى مستوى يوجد اختزال NC ¹ ، ثم اختزال L ، ثم اختزال NC ^{2 ، ثم اختزال} NC ³ ، وهكذا. اتحادها هو اختزال NC . وهي مرتبة لأن${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {NC}}^{3}\subseteq \dots \subseteq {\mathsf {NC}}}$.

في اختزال NC ^k واختزال NC ، يُفرض شرط التوحيد، لأن هدف نظرية اكتمال P هو إثبات الحدود العليا. يُعد عدم التوحيد مفيدًا لإثبات الحدود الدنيا، ولكنه غير مُرضٍ لإثبات الحدود العليا، نظرًا لقوته المفرطة لهذا الغرض. شرط التوحيد القياسي هو التوحيد L ، أي أن عائلة الدوائر يجب أن تكون قابلة للإنشاء بواسطة آلة تورينج، بحيث يكون معطى${\displaystyle 1^{n}}$عند إدخال البيانات، يقوم البرنامج بإخراج وصف لـ${\displaystyle n}$الدائرة رقم - باستخدام${\displaystyle O(\log n)}$شريط عمل. ^{[ 1 ]}

بافتراض لغتين${\displaystyle L,L'}$، يُعرِّف${\displaystyle L\leq _{m}^{{\mathsf {NC}}^{k}}L'}$إذا وفقط إذا وُجدت عائلة دوائر منطقية موحدة من النوع L - NC ^k تقوم مجتمعة بحساب دالة${\displaystyle f:\{0,1\}^{*}\to \{0,1\}^{*}}$بحيث${\displaystyle x\in L}$إذا وفقط إذا${\displaystyle f(x)\in L'}$.

يُعرِّف${\displaystyle L\leq _{m}^{\mathsf {NC}}L'}$إذا وفقط إذا${\displaystyle L\leq _{m}^{{\mathsf {NC}}^{k}}L'}$بالنسبة للبعض${\displaystyle k\geq 1}$.

يُعرِّف${\displaystyle L\leq _{m}^{\mathsf {L}}L'}$إذا وفقط إذا كانت هناك دالة${\displaystyle f:\{0,1\}^{*}\to \{0,1\}^{*}}$ذلك قابل للحساب ضمنيًا في فضاء اللوغاريتم ، بحيث${\displaystyle x\in L}$إذا وفقط إذا${\displaystyle f(x)\in L'}$.

أبسط مشكلة كاملة من النوع P في ظل اختزالات متعددة الواحدات في فضاء اللوغاريتم هي التالية: بالنظر إلى آلة تورينج${\displaystyle M}$، مدخل لتلك الآلة x ، ورقم T (مكتوب بنظام العد الأحادي )،${\displaystyle \langle M,x,T\rangle }$هل تتوقف تلك الآلة عند هذا المدخل خلال أول T خطوة؟ لتقليل${\displaystyle L\in {\mathsf {P}}}$لحل هذه المشكلة، استخدم آلة تورينج${\displaystyle M_{L}}$اتخاذ القرار${\displaystyle L}$في زمن محدود بواسطة متعددة الحدود p . ثم ​​لأي ${\displaystyle x\in L}$، قم بإخراج ترميز${\displaystyle M_{L}}$، وتشفير x نفسه، وعدد من الخطوات${\displaystyle T=p(|x|)}$تتوقف الآلة M عند x ضمن${\displaystyle p(|x|)}$خطوات إذا وفقط إذا كان x في L.

من الواضح أنه إذا استطعنا موازاة محاكاة عامة لحاسوب تسلسلي (أي محاكاة آلة تورينج لآلات تورينج)، فسنتمكن من موازاة أي برنامج يعمل على ذلك الحاسوب. إذا كانت هذه المسألة تنتمي إلى مجموعة NC ، فإن كل مسألة أخرى تنتمي إلى مجموعة P. إذا كُتب عدد الخطوات بالنظام الثنائي، فإن المسألة تكون كاملة من حيث الوقت المُعطى (EXPTIME-complete ). توضح هذه المسألة حيلة شائعة في نظرية اكتمال P. نحن لا نهتم حقًا بما إذا كان بالإمكان حل المسألة بسرعة على جهاز متوازٍ، بل نهتم فقط بما إذا كان الجهاز المتوازٍ يحلها أسرع بكثير من الجهاز التسلسلي. لذلك، علينا إعادة صياغة المسألة بحيث يكون الإصدار التسلسلي منها في مجموعة P. لهذا السبب تطلبت هذه المسألة كتابة T بالنظام الأحادي. إذا كُتب العدد T كعدد ثنائي (سلسلة من n من الآحاد والأصفار، حيث n  =  log T )، فإن الخوارزمية التسلسلية الواضحة يمكن أن تستغرق وقتًا قدره 2^ ⁿ . من جهة أخرى، إذا كُتب T كعدد أحادي (سلسلة من n آحاد، حيث n = T )، فإنه يستغرق وقتًا قدره n فقط . بكتابة T بنظام أحادي بدلًا من ثنائي، نكون قد اختصرنا الخوارزمية التسلسلية الواضحة من زمن أُسّي إلى زمن خطي. هذا يضع المسألة التسلسلية في فئة P. وبالتالي، ستكون في فئة NC إذا وفقط إذا كانت قابلة للتوازي.   

ثبت أن العديد من المسائل الأخرى كاملة من فئة P ، ولذلك يُعتقد على نطاق واسع أنها متسلسلة بطبيعتها. وتشمل هذه المسائل ما يلي، وهي مسائل كاملة من فئة P على الأقل في ظل اختزالات الفضاء اللوغاريتمي، سواء كانت معطاة أو في شكل مسألة قرار:

• مسألة قيمة الدائرة (CVP) - بالنظر إلى دائرة ، ومدخلات الدائرة، وبوابة واحدة في الدائرة، احسب خرج تلك البوابة.
• حالة مقيدة من CVP - مثل CVP، باستثناء أن كل بوابة لها مدخلان ومخرجان (F و Not F)، وكل طبقة أخرى هي بوابات AND فقط، والباقي بوابات OR (أو، بشكل مكافئ، جميع البوابات هي بوابات NAND، أو جميع البوابات هي بوابات NOR)، وتأتي مدخلات البوابة من الطبقة السابقة لها مباشرة
• البرمجة الخطية – تعظيم دالة خطية تخضع لقيود المتباينات الخطية
• ترتيب البحث العمقي أولاً - بالنظر إلى رسم بياني بقوائم تجاور مرتبة ثابتة، وعقدتين u و v ، هل تتم زيارة الرأس u قبل الرأس v في بحث عمقي أولاً ناتج عن ترتيب قوائم التجاور؟ ^{[ 2 ]}
• عضوية القواعد النحوية الخالية من السياق - بالنظر إلى قواعد نحوية خالية من السياق وسلسلة نصية، هل يمكن توليد تلك السلسلة النصية بواسطة تلك القواعد النحوية؟
• إمكانية إرضاء هورن - بالنظر إلى مجموعة من عبارات هورن ، هل يوجد تعيين متغير يحققها؟ هذه هي نسخة P من مشكلة إمكانية الإرضاء المنطقي .
• لعبة الحياة - بالنظر إلى التكوين الأولي للعبة الحياة لكونواي ، وخلية معينة، ووقت T (بنظام العد الأحادي)، هل تبقى تلك الخلية على قيد الحياة بعد T خطوة؟
• ضغط البيانات باستخدام خوارزمية LZW ( نموذج 1978) - بالنظر إلى السلسلتين s و t ، هل سيؤدي ضغط s باستخدام طريقة LZ78 إلى إضافة t إلى القاموس؟ (لاحظ أنه بالنسبة لضغط LZ77 مثل gzip ، يكون هذا أسهل بكثير، حيث تُختزل المشكلة إلى "هل t موجود في s ؟").
• استنتاج النوع للأنواع الجزئية - بالنظر إلى مصطلح غير مصنف من حساب التفاضل والتكامل لامدا ، حدد ما إذا كان لهذا المصطلح نوع جزئي.

معظم اللغات المذكورة أعلاه هي لغات كاملة من النوع P في ظل مفاهيم أقوى للاختزال، مثل الاختزال الموحد.${\displaystyle AC^{0}}$الاختزالات متعددة العناصر، أو اختزالات DLOGTIME، أو الإسقاطات متعددة اللوغاريتمات.

من أجل إثبات أن مشكلة معينة في P هي P- كاملة، يحاول المرء عادة اختزال مشكلة معروفة P- كاملة إلى المشكلة المعطاة.

في عام 1999، ^أظهر جين-يي كاي ودي. سيفاكومار، بالاستناد إلى عمل أوجيهارا، أنه إذا كانت هناك لغة متفرقة كاملة من النوع P ، فإن L  = P. ^{[ 3} ] 

قد تُحل مسائل P- كاملة بأزمنة مختلفة . على سبيل المثال، يمكن حل مسألة قيمة الدائرة في زمن خطي باستخدام فرز طوبولوجي . بالطبع، نظرًا لأن الاختزالات إلى مسألة P- كاملة قد يكون لها أزمنة مختلفة، فإن هذه الحقيقة لا تعني بالضرورة إمكانية حل جميع المسائل في P في زمن خطي أيضًا.

• غرينلو، ريموند، جيمس هوفر، ووالتر روزو. 1995. حدود الحوسبة المتوازية؛ نظرية الاكتمال- P. ISBN 0-19-508591-4— يقوم بتطوير النظرية، ثم يقوم بفهرسة 96 مسألة من مسائل P-Complete .
• ساتورو ميانو وشوجي شيرايشي وتاكايوشي شوداي. قائمة مشاكل P-Complete . جامعة كيوشو، RIFIS-TR-CS-17 . ديسمبر 1990.