ZPP

Na Teoria da complexidade computacional, ZPP (inglês: Zero-error Probabilistic Polinomial time, Probalístico de tempo polinominal sem erros) é a classe complexa de problemas em que uma Máquina de Turing existe com estas propriedades: Sempre retorna a resposta correta SIM ou NÃO. O tempo de execução é irrestrito, mas é polinominal para cada entrada. Em outras palavras, o algoritmo é como o lançamento de uma moeda honesta. Sempre retorna a resposta correta. (Tal algoritmo é chamado de algoritmo Las Vegas.) Para um problema do tamanho n , existe algum p(n) polinominal em que o tempo médio de execução será menor que p(n), ainda que este ocasionalmente demore. Podemos dizer também que, ZPP pode ser definido como a classe de problemas em que uma Máquina de Turing existe com estas propriedades: Sempre executa num tempo polinominal. Sempre retorna SIM, NÃO ou NÃO SEI. A resposta é sempre NÃO SEI ou a correta. Se a resposta e SIM, estão retorna SIM com a probabilidade de pelo menos 1/2. Se a resposta e NÃO, estão retorna NÃO com a probabilidade de pelo menos 1/2. A definição de ZPP é baseada na máquina probabilistica de Turing. Outros clases complexas baseadas nela incluem BPP e RP. A classe BQP é baseada em outra máquina aleatória: o Computador quântico.