Hierarquia polinomial: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 19:
:<math>\Pi_{i+1}^{\rm P} := \mbox{coNP}^{\Sigma_i^{\rm P}}</math>
tal que A<sup>B</sup> é o conjunto de [[Problema de decisão| problemas de decisão]] solucionável por uma [[Máquina de Turing| maquina de
2. Para a definição existencial/universal da definição de hierarquia polinomial, assuma que <math>L</math> seja uma [[Linguagem formal| linguagem]] ( i.e. um problema de decisão, como o sub-conjunto de {0,1}* ), seja <math>P</math> um polinômio e defina:
Linha 49:
Essa definição reflete a conexão forte entre hierarquia polinomial e a [[Hierarquia aritmética]], onde '''[[Linguagem recursiva| R]''' e '''[[Linguagem recursivamente enumerável| RE]]''' são análogas a '''[[P (complexidade)|P]]''' e '''[[NP (complexidade)|NP]]''', respectivamente. A Hierarquia analítica também é definida de forma parecida para dar hierarquia para sub-conjuntos dos números reais.
3. Uma definição equivalente em termos de uma [[Máquina de Turing alternada]] define <math>\Sigma_k^{\rm P}</math> ( respectivamente, <math>\Pi_k^{\rm P}</math> ) como o conjunto de problemas de decisão solvíveis em tempo polinomial em uma máquina de
== Relações entre as classes na hierarquia polinomial ==
| |||