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

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

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

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

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

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

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

تعريف

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

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

امثلة

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

{\displaystyle \operatorname {perm (A)=\sum _{\sigma \in S_{n \prod _{i=1 ^{n a_{i,\sigma (i)

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

خصل القسم P#

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

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

علاقات مع اقسام اخرى

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

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

${\displaystyle NP\subseteq P^{\#P[1]$
${\displaystyle BPP\subseteq P^{\#P[1]$
${\displaystyle {\mbox{co-NP \subseteq P^{\#P[1]$
${\displaystyle P^{\#P[1] \subseteq P^{\#P \subseteq PSPACE$
${\displaystyle {\mbox{PH \subseteq P^{\#P[1] \subseteq P^{\#P$
${\displaystyle FP\subseteq \#P$

حدسيات

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

مسائل كاملة

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