PH(التعقيد الحسابي)

${\displaystyle {\mathcal {PH}}=\cup _{k}\Sigma _{k}^{P}}$ في حين أن ${\displaystyle L\in \Sigma _{k}^{P}}$ إذا يوجد آلة تيورنج كثيرة الحدود قطعية،M, ويوجد متعدد حدود (q(n بحيث أن n هو طول المدخل، ويتحقق: ${\displaystyle x\in L\iff \exists u_{1}\in \{0,1\}^{q(n)}\forall u_{2}\{0,1\}^{q(n)}\cdots Q_{k}u_{k}\in \{0,1\}^{q(n)}M(x,u_{1},u_{2},\cdots ,u_{k})=1}$ في حين أنَّ ${\displaystyle Q_{k}={\begin{cases}\forall ,&{\mbox{if }}k{\mbox{ is even}}\\\exists ,&{\mbox{if }}k{\mbox{ is odd}}\end{cases}}}$

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

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