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

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

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

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

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

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

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

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

تعريف[عدل]

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

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

امثلة[عدل]

  • SAT# هي أحد أهم المسائل التي تتبع هذا القسم وهي : معطى صيغة بوليانية \varphi , جد عدد التعويضات في المتغيرات التي تجعل الصيغة مكتفية .
  • PM# وهي المسالة التي تسأل عن عدد عدد التلائمات التامة (perfect matching) في مخطط ثنائي. لاحظ ان مسألة التقرير الملائمة وهي : هل يوجد في مخطط ثنائي تلائم تام يمكن حلها بواسطة الة تورنج حتمية بوقت حدودي(اي ان المسألة تابعة ل- P ) .
  • فلتكن A مصفوفة ابعادها nxn حيث ان كل الخلايا في المصفوفة اعداد طبيعية اي من المجموعة \mathbb{N} (وليس من المجموعة \mathbb{Z}) نعرف ثابت(permanent) المصفوفة A بالشكل التالي:
 \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}

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

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

  1. P# مغلقة بالنسبة للجمع اي انه لكل f و- g تابعتان ل-P# مجموعهما (f+g) أيضا يتبع P# . اكثر من هذا لكل g\in \# P ولكل عدد ثابت c الدالة : f(x)=\sum_{|y|=|x|^c} g(x,y) أيضا تتبع P# .
  2. P# مغلقة بالنسبة للضرب اي انه لكل f و- g تابعتان ل-P# مجموعهما (f\cdot g) أيضا يتبع P# . اكثر من هذا لكل g\in \# P ولكل عدد ثابت c الدالة : f(x)=\prod_{|y|=c\cdot\log |x|} g(x,y) أيضا تتبع P# .

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

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

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

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

حدسيات[عدل]

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

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

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

مصادر[عدل]

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