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 . A classe BQP é baseada em outra máquina aleatória: o Computador quântico.