سلم P (نظرية التعقيد)

قبل الخوض في التفاصيل، في نظرية التعقيد P# هو صنف عد عدد مسارات الحساب التي هي «موافقة» في آلة تيورنج غير حتمية، وهذا القسم أو الصنف بخلاف كثير من الاقسام هو قسم دوال وليس مسائل تقرير. هناك علاقة قوية بين هذا القسم وبين القسم NP , حيث أن NP صيغة المسألة فيه «هل يوجد حل الذي يحقق ظروف معينة؟» اما P# فالصيغة هي: «ما هو عدد الحلول التي تحقق الظروف؟» مثال:
- المسائل التالية تابعة ل- NP :
- هل يوجد قيم للمتغيرات في صيغة على شكل CNF حيث أنَّ الصيغة المُعطاة مكتفية؟
- هل يوجد في المُخطط المعطى مسار هاميلتوني؟
- هل يوجد مجموعة جزئية لمجموعة اعداد حيث ان مجموع المجموعة الجزئية 0 ؟
- اما مسائل P# فهي كالتالي:
- ما هو عدد التعويضات في القيم لصيغة بشكل CNF التي هي تجعل الصيغة مكتفية؟
- ما هو عدد المسارات الهاملتونية في مخطط معطى؟
- ما هو عدد المجموعات الجزئية التي مجموعها 0 ؟
- لذا فاننا نعلم ان P# هي على الاقل مثل NP .
مسائل كاملة
ومن ناحية أخرى، لهذا القسم الكثير من المسائل الكاملة وهي مسائل يمكن اختصار كل المسائل في P# إلى هذه المسألة وكذلك المسألة نفسها تتبع P# . الامثلة الثلاث المذكورة في الاعلى كلها مسائل كاملة.
خصل القسم P#
إضافةً إلى ذلك، P# مغلقة بالنسبة للجمع أي انه لكل f و- g تابعتان ل-P# مجموعهما (f+g) كذلك يتبع P# . أكثر من هذا لكل ولكل عدد ثابت c الدالة: كذلك تتبع P# .
ملاحظة: P# ليست مغلقة بالنسبة للطرح.
من جانب آخر، P# مغلقة بالنسبة للضرب اي انه لكل f و- g تابعتان ل-P# مجموعهما (f g) كذلك يتبع P# . أكثر من هذا لكل ولكل عدد ثابت c الدالة: كذلك تتبع P# .
حدسيات
من جهة ثانية، لعل أحد أهم الحدسيات في علوم الحاسوب والرياضيات هي NP≠P مسألة مشابهة ولا تقل اهمية هي المسألة P≠PP , القسم PP هو قسم مسائل التقرير التي جوابها نعم إذا كان أكثر من نصف مسارات الحساب «موافقة», ويتحقق NP⊆PP , وهذه المسألة الاخيرة ترتبط ارتباطا وثيقا مع المسألة FP ≠ #P إذ انهما متكافئتان أي ان الحدسية الأولى صحيحة إذا وفقط إذا الحدسية الثانية صحيحة.
امثلة
علاوةً على ذلك، حيث ان هي مجموعة كل التباديل المجموعة . لاحظ ان ثابت المصفوفة مشابه إلى حد كبير محدد المصفوفة، للوهلة الأولى من الصعب رؤية لم هذه المسألة تابعة ل- P# ولكن تبين ان حساب ثابت المصفوفة يعني حساب عدد التلائمات التامة في مُخطط وكما قلنا ان المسألة الاخيرة تتبع القسم P# بلا ريب.
إضافةً إلى ذلك، PM# وهي المسالة التي تسأل عن عدد عدد التلائمات التامة (perfect matching) في مخطط ثنائي. لاحظ ان مسألة التقرير الملائمة وهي: هل يوجد في مخطط ثنائي تلائم تام يمكن حلها بواسطة آلة تورنغ حتمية بوقت حدودي (أي ان المسألة تابعة ل- P).
كذلك، فلتكن A مصفوفة ابعادها nxn حيث ان كل الخلايا في المصفوفة اعداد طبيعية أي من المجموعة (وليس من المجموعة ) نعرف ثابت (permanent) المصفوفة A بالشكل التالي:
علاوةً على ذلك، SAT# هي أحد أهم المسائل التي تتبع هذا القسم وهي: معطى صيغة بوليانية , جد عدد التعويضات في المتغيرات التي تجعل الصيغة مكتفية.
علاقات مع اقسام أخرى
, هذه العلاقة تسمى كذلك مبرهنة تودا.
حينها يتحقق التالي:
إضافةً إلى ذلك، أغلب الاقسام المعروفة هي اقسام مسائل تقرير لذا حتى نستطيع المقارنة بين هذه الاقسام و-P# وجب علينا جعل P# اوراكل، لذا فاننا نعرف القسم التالي: والذي هو قسم كل المسائل التي يمكن حلها بواسطة آلة تورنغ حتمية مع امكانية الدخول إلى P# على انه اوراكل. كما اننا نعرف القسم التالي: والذي هو قسم كل المسائل التي يمكن حلها بواسطة آلة تورنغ حتمية مع امكانية الدخول إلى P# على انه اوراكل لمرة واحدة فقط.
قسم تعقيد
نظرية التعقيد الحسابي.
مسألة P=NP
تعريف
وعلى صعيد آخر، لذا فان P# هي مجموعة كل الدوال التي يمكن حسابها بواسطة آلة تورنغ عدادة في وقت كثير الحدود.
علاوةً على ذلك، حتى نعرف هذا القسم تعريفا دقيقا نلاحظ ان نموذج آلة تورنغ الاعتيادي ليس ملائما لذا فاننا بحاجة لتعريف يتلائم مع المجموعة، لذا فاننا نعرف آلة تورنغ عدادة وهي آلة تيورنج غير حتمية والتي مُخرجها عند اعطائها مُدخل x هو عدد المسارات الموافقة لذلك المدخل.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟