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

حتى نعرف هذا القسم تعريفا دقيقا نلاحظ ان نموذج آلة تورنغ الاعتيادي ليس ملائما لذا فاننا بحاجة لتعريف يتلائم مع المجموعة، لذا فاننا نعرف آلة تورنغ عدادة وهي آلة تيورنج غير حتمية والتي مُخرجها عند اعطائها مُدخل 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# بلا ريب.

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

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

• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية

• بوابة برمجة الحاسوب
• بوابة رياضيات
• بوابة علم الحاسوب