Класс PH
Sign in to saveAlso 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 (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу или . Также говорят, что язык, распознаваемый таким предикатом (то есть множество всех слов, на которых предикат возвращает 1), принадлежит классу PH.
Abstract from DBpedia / Wikipedia · CC BY-SA