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