في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود.[1] لقد تم تعريف هذا القسم لأول مرة بواسطة لاري ستوكماير. وهذا القسم يتبع P#P = PPP وكذلك يتبع بيسبايس.
PH يحتوي معظم الاقسام في بيسبايس مثل: NP ,P,كو-إن بي كما أنه يحوي اقسام تعقيد احتمالية مثل: BPP , RP , ولكن هناك دلائل على أنَّ BQP لا يتبع PH .
P=NP إذا وفقط إذا PH=P لذا فانه كفاية أن يُبرهن أنَّ P≠PH لكي نبرهن أن P≠NP .
تعريف
في حين أن إذا يوجد آلة تيورنج كثيرة الحدود قطعية،M, ويوجد متعدد حدود (q(n بحيث أن n هو طول المدخل، ويتحقق: في حين أنَّ
مراجع
انظر أيضا
أقسام التعقيد المهمة |
---|
ممكنة للتنفيذ | |
---|
مشكوك في إمكانية تنفيذها | |
---|
غير قابل للتنفيذ | |
---|
أقسام هرمية | |
---|
عائلات اقسام | |
---|