Also known as Polynomial Hierarchy
algorithmic complexity class; the union of all complexity classes in the polynomial hierarchy; the set of languages expressible by second-order logic
Wikidata facts
- Instance of
- complexity class
- Subclass of
- computational problem
- Part of
- PSPACE
- Named after
- polynomial hierarchy
Show 1 more fact
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · العربية
في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود. لقد تم تعريف هذا القسم لأول مرة بواسطة لاري ستوكماير. وهذا القسم يتبع P#P = P وكذلك يتبع بيسبايس. PH يحتوي معظم الاقسام في بيسبايس مثل: NP ,P,كو-إن بي كما أنه يحوي اقسام تعقيد احتمالية مثل: BPP , RP , ولكن هناك دلائل على أنَّ لا يتبع PH . P=NP إذا وفقط إذا PH=P لذا فانه كفاية أن يُبرهن أنَّ P≠PH لكي نبرهن أن P≠NP .
Abstract from DBpedia / Wikipedia · CC BY-SA