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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في نظرية التعقيد P# هو صنف عد عدد مسارات الحساب التي هي "موافقة" في الة تيورنج غير حتمية , وهذا القسم او الصنف بخلاف كثير من الاقسام هو قسم دوال وليس مسائل تقرير . هناك علاقة قوية بين هذا القسم وبين القسم NP , حيث أن NP صيغة المسألة فيه "هل يوجد حل الذي يحقق ظروف معينة؟" اما P# فالصيغة هي : "ما هو عدد الحلول التي تحقق الظروف ؟" مثال :

المسائل التالية تابعة ل- NP :

  • هل يوجد قيم للمتغيرات في صيغة على شكل CNF حيث أنَّ الصيغة المُعطاة مكتفية ؟
  • هل يوجد في المُخطط المعطى مسار هاميلتوني ؟
  • هل يوجد مجموعة جزئية لمجموعة اعداد حيث ان مجموع المجموعة الجزئية 0 ؟

اما مسائل P# فهي كالتالي :

  • ما هو عدد التعويضات في القيم لصيغة بشكل CNF التي هي تجعل الصيغة مكتفية ؟
  • ما هو عدد المسارات الهاملتونية في مخطط معطى ؟
  • ما هو عدد المجموعات الجزئية التي مجموعها 0 ؟

لذا فاننا نعلم ان P# هي على الاقل مثل NP .

تعريف[عدل]

حتى نعرف هذا القسم تعريفا دقيقا نلاحظ ان نموذج الة تورنج الاعتيادي ليس ملائما لذا فاننا بحاجة لتعريف يتلائم مع المجموعة , لذا فاننا نعرف الة تورنج عدادة وهي الة تيورنج غير حتمية والتي مُخرجها عند اعطائها مُدخل x هو عدد المسارات الموافقة لذلك المدخل .

لذا فان P# هي مجموعة كل الدوال التي يمكن حسابها بواسطة الة تورنج عدادة في وقت كثير الحدود .

امثلة[عدل]

  • SAT# هي أحد أهم المسائل التي تتبع هذا القسم وهي : معطى صيغة بوليانية , جد عدد التعويضات في المتغيرات التي تجعل الصيغة مكتفية .
  • PM# وهي المسالة التي تسأل عن عدد عدد التلائمات التامة (perfect matching) في مخطط ثنائي. لاحظ ان مسألة التقرير الملائمة وهي : هل يوجد في مخطط ثنائي تلائم تام يمكن حلها بواسطة الة تورنج حتمية بوقت حدودي(اي ان المسألة تابعة ل- P ) .
  • فلتكن A مصفوفة ابعادها nxn حيث ان كل الخلايا في المصفوفة اعداد طبيعية اي من المجموعة (وليس من المجموعة ) نعرف ثابت(permanent) المصفوفة A بالشكل التالي:

حيث ان هي مجموعة كل التباديل المجموعة . لاحظ ان ثابت المصفوفة مشابه إلى حد كبير محدد المصفوفة ,للوهلة الاولى من الصعب رؤية لم هذه المسألة تابعة ل- P# ولكن تبين ان حساب ثابت المصفوفة يعني حساب عدد التلائمات التامة في مُخطط وكما قلنا ان المسألة الاخيرة تتبع القسم P# بلا ريب .

خصل القسم P#[عدل]

  1. P# مغلقة بالنسبة للجمع اي انه لكل f و- g تابعتان ل-P# مجموعهما (f+g) أيضا يتبع P# . اكثر من هذا لكل ولكل عدد ثابت c الدالة : أيضا تتبع P# .
  2. P# مغلقة بالنسبة للضرب اي انه لكل f و- g تابعتان ل-P# مجموعهما (f g) أيضا يتبع P# . اكثر من هذا لكل ولكل عدد ثابت c الدالة : أيضا تتبع P# .

ملاحظة : P# ليست مغلقة بالنسبة للطرح .

علاقات مع اقسام اخرى[عدل]

معظم الاقسام المعروفة هي اقسام مسائل تقرير لذا حتى نستطيع المقارنة بين هذه الاقسام و-P# وجب علينا جعل P# اوراكل , لذا فاننا نعرف القسم التالي : والذي هو قسم كل المسائل التي يمكن حلها بواسطة الة تورنج حتمية مع امكانية الدخول إلى P# على انه اوراكل . كما اننا نعرف القسم التالي : والذي هو قسم كل المسائل التي يمكن حلها بواسطة الة تورنج حتمية مع امكانية الدخول إلى P# على انه اوراكل لمرة واحدة فقط.

حينها يتحقق التالي :

  • , هذه العلاقة تسمى أيضا مبرهنة تودا .

حدسيات[عدل]

لعل أحد أهم الحدسيات في علوم الحاسوب والرياضيات هي NPP مسألة مشابهة ولا تقل اهمية هي المسألة PPP , القسم PP هو قسم مسائل التقرير التي جوابها نعم اذا كان اكثر من نصف مسارات الحساب "موافقة" , ويتحقق NPPP , وهذه المسألة الاخيرة ترتبط ارتباطا وثيقا مع المسألة FP#P إذ انهما متكافئتان اي ان الحدسية الاولى صحيحة اذا وفقط اذا الحدسية الثانية صحيحة .

مسائل كاملة[عدل]

لهذا القسم العديد من المسائل الكاملة وهي مسائل يمكن اختصار كل المسائل في P# إلى هذه المسألة وكذلك المسألة نفسها تتبع P# . الامثلة الثلاث المذكورة في الاعلى كلها مسائل كاملة .

مصادر[عدل]

انظر أيضا[عدل]