في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة.
نعرف الاقسام التالية:
Σ
1
=
NP
{\displaystyle \Sigma _{1}={\mbox{NP}}}
وبطريقة البناء عن طريق الاستقراء نعرف:
Σ
i
=
NP
Σ
i
−
1
{\displaystyle \Sigma _{i}={\mbox{NP}}^{\Sigma _{i-1}}}
في حين أنَّ:
NP
C
{\displaystyle {\mbox{NP}}^{C}}
هي مجموعة اللغات التي يمكن تقريرها بواسطة آلة تيورنج كثيرة الحدود غير قطعية مع امكانية الدخول إلى اوراكل من القسم C .
حينها:
PH
=
∪
i
=
0
∞
Σ
i
{\displaystyle {\mbox{PH}}=\cup _{i=0}^{\infty }\Sigma _{i}}
2. نعرف القسم
Σ
i
{\displaystyle \Sigma _{i}}
بشكل اخر:
L
∈
Σ
i
{\displaystyle {\mbox{L}}\in \Sigma _{i}}
إذا يوجد علاقة محدودة بكثير حدود وقابلة للتمييز بوقت كثير الحدود مع i+1 متغيرات حيث أنَّ:
x
∈
L
⟺
∃
y
1
∀
y
2
⋯
Q
i
y
i
(
x
,
y
1
,
y
2
,
⋯
,
y
i
)
∈
R
L
{\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\cdots Q_{i}y_{i}(x,y_{1},y_{2},\cdots ,y_{i})\in R_{L}}
في حين أنَّ
Q
i
=
{
∀
,
if
i
is even
∃
,
if
i
is odd
{\displaystyle Q_{i}={\begin{cases}\forall ,&{\mbox{if }}i{\mbox{ is even}}\\\exists ,&{\mbox{if }}i{\mbox{ is odd}}\end{cases}}}
يمكن ان نبين أنَّ التعريفان متكافئان وذلك بواسطة الاستقراء لكل i .
على غرار co-NP , P يمكن تعريف اقسام مشابهة وهي:
Δ
1
=
P
{\displaystyle \Delta _{1}={\mbox{P}}}
Δ
i
=
P
Δ
i
−
1
{\displaystyle \Delta _{i}={\mbox{P}}^{\Delta _{i-1}}}
Π
1
=
co-NP
{\displaystyle \Pi _{1}={\mbox{co-NP}}}
Π
i
=
co-NP
Π
i
−
1
{\displaystyle \Pi _{i}={\mbox{co-NP}}^{\Pi _{i-1}}}
ويمكن تعريف PH بواسطة
Δ
i
{\displaystyle \Delta _{i}}
أو بواسطة
Π
i
{\displaystyle \Pi _{i}}
وذلك لانَّ:
Π
i
⊆
Σ
i
+
1
{\displaystyle \Pi _{i}\subseteq \Sigma _{i+1}}
Σ
i
⊆
Π
i
+
1
{\displaystyle \Sigma _{i}\subseteq \Pi _{i+1}}
Σ
i
∪
Π
i
⊆
Δ
i
⊆
Σ
i
+
1
∩
Π
i
+
1
{\displaystyle \Sigma _{i}\cup \Pi _{i}\subseteq \Delta _{i}\subseteq \Sigma _{i+1}\cap \Pi _{i+1}}
نقول أنَّ PH انهارت إذا تحقق التالي:
يوجد k بحيث أنَّ
Σ
k
=
Σ
k
+
1
{\displaystyle \Sigma _{k}=\Sigma _{k+1}}
حيث أنه إذا وجد k كهذا حينها:
Σ
k
=
PH
{\displaystyle \Sigma _{k}={\mbox{PH}}}
واغلب علماء الحاسوب والرياضيات يقولون بعدم انهيار الهرم كثير الحدود، ومع هذا فإنه غير معلوم إذا ما PH مُنهار أو لا !
علاقات مع اقسام أخرى[ عدل ]
يمكن بسهولة تبيين أنَّ
PH
⊆
PSPACE
{\displaystyle {\mbox{PH}}\subseteq {\mbox{PSPACE}}}
. وذلك لاننا يمكننا تجربة كل الامكانيات كما في تعريف PH ونستخدم مساحة اضافية متعددة الحدود.
إذا
NP
=
coNP
{\displaystyle {\mbox{NP}}={\mbox{coNP}}}
حينها
PH=NP
{\displaystyle {\mbox{PH=NP}}}
لكل i إذا
Σ
i
=
Π
i
{\displaystyle \Sigma _{i}=\Pi _{i}}
حينها
PH
=
Σ
i
{\displaystyle {\mbox{PH}}=\Sigma _{i}}
مبرهنة سبسر ولوتومان:
BPP
⊆
PH
{\displaystyle {\mbox{BPP}}\subseteq {\mbox{PH}}}
إذا
NP
⊆
P/Poly
{\displaystyle {\mbox{NP}}\subseteq {\mbox{P/Poly}}}
حينها:
Σ
2
=
Π
2
{\displaystyle \Sigma _{2}=\Pi _{2}}
أي انه
PH
=
Σ
2
{\displaystyle {\mbox{PH}}=\Sigma _{2}}
.
مبرهنة كانان: لكل k،
Σ
2
{\displaystyle \Sigma _{2}}
لا يتبع القسم: (Size (nk
مبرهنة تودا:
PH
⊆
P
#
P
{\displaystyle {\mbox{PH}}\subseteq P^{\#P}}
لكل Σi يمكن تعريف المسألة التالية: Σi SAT :
المعطى: صيغة
φ
(
x,y
)
{\displaystyle \varphi ({\mbox{x,y}})}
والتي هي بشكل SAT
المخرج: هل صحيح أنَّ:
∃
x
∀
y
1
∃
y
2
⋯
Q
i
y
i
φ
(
x
,
y
1
,
⋯
,
y
i
)
{\displaystyle \exists x\forall y_{1}\exists y_{2}\cdots Q_{i}y_{i}\varphi ({\mbox{x}},{\mbox{y}}_{1},\cdots ,{\mbox{y}}_{i})}
حيث أنَّ:
Q
i
=
{
∀
,
if
i
is even
∃
,
if
i
is odd
{\displaystyle Q_{i}={\begin{cases}\forall ,&{\mbox{if }}i{\mbox{ is even}}\\\exists ,&{\mbox{if }}i{\mbox{ is odd}}\end{cases}}}
هذه المسألة كاملة ل-
Σ
i
{\displaystyle \Sigma _{i}}
. يمكن ايجاد مسائل أخرى كاملة [ 1] في الهامش.
لنفرض أن المسألة L هي كاملة في PH ، حينها يوجد k بحيث أنَّ
L
∈
Σ
k
{\displaystyle {\mbox{L}}\in \Sigma _{k}}
وبما أن هذه المسألة كاملة كل مسألة في PH يمكن اختزالها لهذه المسألة أي L ومن ضمن هذه المسائل نأخذ المسائل التي تتبع
Σ
k
+
1
{\displaystyle \Sigma _{k+1}}
حينها كل مسألة كهذه تتبع أيضا
Σ
k
{\displaystyle \Sigma _{k}}
وهذا يعني أنَّ
Σ
k
+
1
⊆
Σ
k
{\displaystyle \Sigma _{k+1}\subseteq \Sigma _{k}}
وهذا يعني أنَّ
P
H
=
Σ
k
{\displaystyle PH=\Sigma _{k}}
وهذا يعني أنَّ الهرم كثير الحدود ينهار ! لذا لا يمكن أن يكون هنالك مسائل كاملة الا إذا انهار PH . وهذا يعطي دليلا أنَّ PH و-PSPACE لا يمكن ان يكونا متساويتيين!
أقسام التعقيد المهمة
ممكنة للتنفيذ مشكوك في إمكانية تنفيذها غير قابل للتنفيذ أقسام هرمية عائلات اقسام