سلم 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#

P# مغلقة بالنسبة للجمع أي انه لكل f و- g تابعتان ل-P# مجموعهما (f+g) أيضا يتبع P# . أكثر من هذا لكل $g\in \#P$ ولكل عدد ثابت c الدالة: $f(x)=\sum _{|y|=|x|^{c}}g(x,y)$ أيضا تتبع P# .
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# على انه اوراكل لمرة واحدة فقط.

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

$NP\subseteq P^{\#P[1]}$
$BPP\subseteq P^{\#P[1]}$
${\mbox{co-NP}}\subseteq P^{\#P[1]}$
$P^{\#P[1]}\subseteq P^{\#P}\subseteq PSPACE$
${\mbox{PH}}\subseteq P^{\#P[1]}\subseteq P^{\#P}$ , هذه العلاقة تسمى أيضا مبرهنة تودا.
$FP\subseteq \#P$

حدسيات

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

مسائل كاملة

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

مصادر

http://pages.cs.wisc.edu/~dieter/Courses/2010s-CS710/Scribes/PDF/lecture22.pdf

انظر أيضا