P (التعقيد)

في نظرية التعقيد الحسابي ، تُعدّ P ، والمعروفة أيضًا باسم PTIME أو DTIME ( حيث n ≤ ^{O(1) )،} فئة تعقيد أساسية . وهي تشمل جميع مسائل القرار التي يمكن حلها بواسطة آلة تورينج حتمية باستخدام وقت حسابي متعدد الحدود ، أو وقت متعدد الحدود .

تنص أطروحة كوبام على أن P هي فئة المسائل الحسابية التي يمكن حلها بكفاءة أو يمكن التعامل معها بسهولة . هذا ليس دقيقًا تمامًا: ففي الواقع، بعض المسائل التي لا يُعرف أنها تنتمي إلى P لها حلول عملية، وبعض المسائل التي تنتمي إلى P ليس لها حلول عملية، ولكن هذه قاعدة عامة مفيدة .

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

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

يمكن أيضًا النظر إلى P على أنها عائلة موحدة من الدوائر المنطقية . تنتمي اللغة L إلى P إذا وفقط إذا وُجدت عائلة موحدة من الدوائر المنطقية ذات زمن متعدد الحدود.${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$بحيث

• للجميع${\displaystyle n\in \mathbb {N} }$،${\displaystyle C_{n}}$يأخذ n بت كمدخلات ويخرج بت واحد
• لكل x في L ،${\displaystyle C_{|x|}(x)=1}$
• لكل x ليس في L ،${\displaystyle C_{|x|}(x)=0}$

يمكن تبسيط تعريف الدائرة بحيث يستخدم فقط عائلة موحدة من فضاء لوغاريتمي دون تغيير فئة التعقيد.

من المعروف أن مجموعة مسائل P تحتوي على العديد من المسائل الطبيعية، بما في ذلك مسائل اتخاذ القرار في البرمجة الخطية ، وإيجاد المطابقة القصوى . في عام 2002، تم إثبات أن مسألة تحديد ما إذا كان عدد ما أوليًا تندرج ضمن مجموعة مسائل P. ^{[ 1 ]} أما فئة مسائل الدوال ذات الصلة فهي FP .

تُعتبر العديد من المشكلات الطبيعية كاملة بالنسبة لـ P، بما في ذلك الاتصال من النوع st (أو إمكانية الوصول ) على الرسوم البيانية المتناوبة ^{[ 2 ].} وتسرد المقالة المتعلقة بالمشكلات الكاملة من النوع P المزيد من المشكلات ذات الصلة في P.

يُعدّ NP تعميمًا لـ P ، وهو فئة مسائل القرار التي يمكن حلّها بواسطة آلة تورينغ غير حتمية تعمل في وقت متعدد الحدود . وبصورة مكافئة، هي فئة مسائل القرار التي يكون لكل حالة "نعم" فيها شهادة ذات حجم متعدد الحدود، ويمكن التحقق من الشهادات بواسطة آلة تورينغ حتمية تعمل في وقت متعدد الحدود. تُسمى فئة المسائل التي ينطبق عليها هذا بالنسبة لحالات "لا" co-NP . من البديهي أن P مجموعة جزئية من NP و co-NP؛ ويعتقد معظم الخبراء أنها مجموعة جزئية فعلية، ^{[ 3 ]} على الرغم من أن هذا الاعتقاد (${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$لا تزال الفرضية غير مثبتة . ومن المشكلات المفتوحة الأخرى ما إذا كان NP  =  co-NP؛ بما أن P = co-P، ^{[ 4 ]} فإن الإجابة السلبية ستعني${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$.

من المعروف أيضًا أن P لا يقل حجمه عن L ، وهي فئة المسائل القابلة للحل في مساحة ذاكرة لوغاريتمية . يستخدم جهاز اتخاذ القرار${\displaystyle O(\log n)}$لا يمكن استخدام المساحة لأكثر من${\displaystyle 2^{O(\log n)}=n^{O(1)}}$الوقت، لأنه يمثل العدد الإجمالي للتكوينات الممكنة؛ وبالتالي، فإن L هي مجموعة جزئية من P. وثمة مشكلة أخرى مهمة تتمثل في ما إذا كانت L = P. نعلم أن P = AL، وهي مجموعة المسائل القابلة للحل في ذاكرة لوغاريتمية بواسطة آلات تورينج المتناوبة . ومن المعروف أيضًا أن P لا تتجاوز PSPACE ، وهي فئة المسائل القابلة للتقرير في فضاء متعدد الحدود. وتُكافئ PSPACE مجموعة NPSPACE وفقًا لنظرية سافيتش . ومرة ​​أخرى، يبقى ما إذا كانت P = PSPACE مسألة مفتوحة. باختصار:

${\displaystyle {\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}={\mathsf {NPSPACE}}\subseteq {\mathsf {EXPTIME}}.}$

هنا، يُمثل EXPTIME فئة المسائل القابلة للحل في وقت أُسّي. من بين جميع الفئات الموضحة أعلاه، لا يُعرف سوى حالتي احتواء صارمتين:

• P محصورة بشكل صارم في EXPTIME. وبالتالي، فإن جميع المشكلات الصعبة في EXPTIME تقع خارج P، وواحد على الأقل من القيود الموجودة على يمين P أعلاه صارم (في الواقع، يُعتقد على نطاق واسع أن القيود الثلاثة جميعها صارمة).
• L محصورة بشكل صارم في PSPACE.

أصعب المشاكل في P هي مشاكل P-كاملة .

يُعدّ P/poly ، أو مسألة الوقت متعدد الحدود غير المنتظم، تعميمًا آخر لمسألة P. إذا كانت المسألة تنتمي إلى P/poly، فيمكن حلّها في وقت متعدد الحدود حتمي، شريطة توفير سلسلة توجيهات تعتمد فقط على طول المُدخلات. على عكس مسألة NP، لا تحتاج آلة الوقت متعدد الحدود إلى كشف سلاسل التوجيهات المُزيّفة؛ فهي ليست أداة تحقق. تُشكّل P/poly فئة واسعة تضمّ جميع المسائل العملية تقريبًا، بما في ذلك جميع مسائل BPP . إذا احتوت على NP، فإن التسلسل الهرمي متعدد الحدود ينهار إلى المستوى الثاني. من ناحية أخرى، تحتوي أيضًا على بعض المسائل غير العملية، بما في ذلك بعض المسائل غير القابلة للحسم ، مثل النسخة الأحادية لأي مسألة غير قابلة للحسم.

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

P موجود في BQP ؛ من غير المعروف ما إذا كان هذا الاحتواء صارمًا.

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

اللغات في P مغلقة أيضًا تحت عمليات الانعكاس، والتقاطع ، والاتحاد ، والتسلسل ، وإغلاق كلين ، والتشاكل العكسي ، والمكملة . ^{[ 6 ]}

من المعروف أن بعض المسائل قابلة للحل في زمن متعدد الحدود، ولكن لا توجد خوارزمية محددة معروفة لحلها. على سبيل المثال، تضمن نظرية روبرتسون-سيمور وجود قائمة منتهية من القواسم الصغرى المحظورة التي تميز (على سبيل المثال) مجموعة الرسوم البيانية التي يمكن تضمينها على سطح حلقي؛ علاوة على ذلك، أثبت روبرتسون وسيمور وجود خوارزمية من رتبة O( n³ ⁾ لتحديد ما إذا كان رسم بياني ما يحتوي على رسم بياني معين كقاموس صغري. وهذا يُقدم برهانًا غير بنائي على وجود خوارزمية متعددة الحدود لتحديد ما إذا كان من الممكن تضمين رسم بياني معين على سطح حلقي، على الرغم من عدم وجود خوارزمية محددة معروفة لهذه المسألة.

في مجال التعقيد الوصفي ، يمكن وصف P بأنها المسائل القابلة للتعبير عنها في منطق الرتبة الأولى (LOFP) ، مع إضافة عامل النقطة الثابتة الصغرى إليه، على البنى المرتبة. في كتاب إيمرمان الدراسي لعام 1999 حول التعقيد الوصفي، ^{[ 7 ]} ينسب إيمرمان هذه النتيجة إلى فاردي ^{[ 8 ]} وإلى إيمرمان عام 1982. ^{[ 9 ]}

في عام 1992، قدم بيلانتوني وكوك توصيفًا بديلًا لـ FP ^{[ 10 ]} ، حيث قاما بتعريف الدوال القابلة للحساب في وقت متعدد الحدود باستخدام مخطط تكرار آمن، مما يوفر تعريفًا هيكليًا مستقلًا عن الآلة ضمن إطار التعقيد الحسابي الضمني . ^{[ 11 ]}

نُشر في عام 2001 أن PTIME يتوافق مع قواعد ربط النطاق (الإيجابية) . ^{[ 12 ]}

يمكن تعريف P أيضًا على أنها فئة تعقيد خوارزمي للمسائل التي لا تُعدّ مسائل قرار ^{[ 13 ]} (على الرغم من أن إيجاد حل لمسألة إرضاء من الدرجة 2 في وقت متعدد الحدود، على سبيل المثال، يُعطي تلقائيًا خوارزمية متعددة الحدود لمسألة القرار المقابلة). في هذه الحالة، لا تُعدّ P مجموعة جزئية من NP، ولكن${\displaystyle P\cap DEC}$هو، حيث${\displaystyle DEC}$هي فئة من مسائل اتخاذ القرار.

يذكر كوزين ^{[ 14 ]} أن كوبهام وإدموندز "يُنسب إليهما عمومًا ابتكار مفهوم الوقت متعدد الحدود"، على الرغم من أن رابين ابتكر هذا المفهوم أيضًا بشكل مستقل وفي نفس الفترة تقريبًا (نُشرت ورقة رابين ^{[ 15 ]} في وقائع مؤتمر عام 1966، بينما نُشرت ورقة كوبهام ^{[ 16 ]} في وقائع مؤتمر عام 1964، ونُشرت ورقة إدموندز ^{[ 17 ]} في مجلة عام 1965، مع أن رابين لم يذكر أيًا منهما ويبدو أنه لم يكن على علم بهما). ^{[ 18 ]} ابتكر كوبهام هذه الفئة كطريقة فعالة لتوصيف الخوارزميات الفعالة، مما أدى إلى أطروحته . ومع ذلك، قام إتش سي بوكلينجتون ، في ورقة بحثية عام 1910، ^{[ 19 ] [ 20 ]} بتحليل خوارزميتين لحل التطابقات التربيعية، ولاحظ أن إحداهما استغرقت وقتًا "يتناسب مع قوة لوغاريتم المعيار" وقارن ذلك بأخرى استغرقت وقتًا يتناسب "مع المعيار نفسه أو جذره التربيعي"، وبالتالي رسم تمييز صريح بين خوارزمية تعمل في وقت متعدد الحدود مقابل أخرى تعمل في وقت أسي (بشكل معتدل).

• مدخل "نظرية التعقيد الحسابي"بقلم والتر دين، في موسوعة ستانفورد للفلسفة ، خريف 2021
• موقع Stack Overflow. "نظرية التعقيد - لماذا co-P = P؟" . موقع Stack Overflow . تم الاطلاع عليه بتاريخ 15 نوفمبر 2025 .
• حديقة حيوانات التعقيد : الفئة P
• حديقة التعقيد : الفئة P/متعددة الأوجه