ZPP (complexidade)
A aula ZPP , é um objeto da teoria da complexidade , em ciência da computação teórica . É uma classe de problemas de decisão na máquina de Turing probabilística . A sigla ZPP vem de Zero-Error Probabilistic Polynomial time .
Definições
Existem várias definições equivalentes de ZPP. Começamos com aquele que lhe dá o nome.
Definição pelo tempo polinomial na expectativa
A classe ZPP é o conjunto de problemas, ou linguagens equivalentes , para os quais existe uma máquina de Turing probabilística , como:
- A máquina não se engana: ela rejeita as palavras que não estão na língua e aceita as que lhe pertencem (como para uma classe não probabilística).
- O tempo de cálculo é polinomial na expectativa .
Definições com a resposta "Não sei"
ZPP é a classe de problemas que podem ser resolvidos em uma máquina de Turing de tempo polinomial probabilística com as seguintes propriedades:
- Ela responde Sim, Não ou Não Sei.
- Se a resposta for Sim, então a palavra está no idioma; se for não, não está.
- Ela responde Não Sei com uma probabilidade menor ou igual a 1/2.
Definição por interseção
A classe ZPP também é a interseção das classes RP e co-RP :
Relações com outras classes
Por definição: .
E também temos: P .
Problemas em ZPP
História
Esta aula foi introduzida por J. Gill no artigo Complexidade computacional de máquinas de Turing probabilísticas , ao mesmo tempo que a aula RP .
Bibliografia
(pt) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 7
Link externo
Notas e referências
- Complexity Zoo
- (em) John Gill , " Computational complex of probabilistic Turing machine " , SIAM Journal we Computing , vol. 6, n o 4, 1977, p. 675-695