PP (complexidade): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m traduzindo nome/parâmetro nas citações, outros ajustes usando script |
Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel |
||
Linha 1:
Em [[Complexidade computacional]], PP é a classe de problemas de decisão decidíveis por uma [[Máquina de Turing probabilística]] em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instancias. A abreviação PP se refere a tempo polinomial probabilístico. A classe de complexidade foi definida<ref>J. Gill, "Computational complexity of probabilistic Turing machines." ''SIAM Journal on Computing'', 6 (4), pp. 675–695, 1977.</ref> por Gill em 1977.
Se um problema de decisão está em PP, então existe um algorítimo para ele que se permite "jogar moedas para cima" e tomar decisões aleatórias. É garantido que ele rode em tempo polinomial. Se a resposta é SIM, o algoritmo vai responder SIM com uma probabilidade maior do que 1/2. Se a resposta for NÃO, o algoritmo vai responder SIM com uma probabilidade menor ou igual a 1/2. Em termos mais práticos, ela é a classe dos problemas que podem ser decididos para qualquer grau de precisão fixo rodando um
Uma caracterização alternativa para PP é o conjunto de problemas que pode ser resolvido por uma [[Máquina de Turing não determinística]] em tempo polinomial onde a condição de aceitação é que a maioria(mais da metade) dos caminhos de computação são aceitos. Por causa disso, alguns autores sugerem o nome alternativo Majority-P<ref>Lance Fortnow. Computational Complexity: Wednesday, September 4, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html</ref>
| |||