Complexidade 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
In the Vinony graph
Within Vinony's link graph, Complexidade PH connects to symbol and polynomial hierarchy.
Its subject is documented across 12 Wikipedia language editions.
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 · Português
Na teoria da complexidade computacional, a classe de complexidade de PH é a união de todas as classes de complexidade na hierarquia polinomial: O PH foi primeiramente definido por Larry Stockmeyer. é um caso especial de hierarquia de limitado alternando máquina de Turing. Ele está contido em P#P = PPP (por Toda teorema; a classe de problemas que são decidível por um tempo polinomial máquina de Turing com acesso a um #P ou equivalentemente PP oracle), e também em PSPACE. O PH tem uma simples lógica de caracterização: é o conjunto de idiomas que podem ser expressadas através de segunda ordem lógica. PH contém quase todas as classes conhecidas de complexidade dentro de PSPACE; em particular, contém P, NPe co-NP. Ele ainda contém classes probabilística como BPP e RP. No entanto, há algumas evidências de que BQP, a classe de problemas resolvidos em tempo polinomial por um computador quântico, não está contido no PH. P = NP se e somente se P = PH. Isso pode simplificar a um potencial de prova de P ≠ NP, pois só é necessário separar a P a partir do mais geral da classe de PH.
Abstract from DBpedia / Wikipedia · CC BY-SA