Este artigo não cita fontes confiáveis. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: Google (N • L • A • I • WP refs)  • ABW  • CAPES (dezembro de 2011)

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.

A classe ZPP é exatamente igual a interseção das classes RP e Co-RP. Esta é frequentemente tomada como a definição de ZPP. Para mostrar isto, primeiro repare que todo problema que é ao mesmo tempo RP e co-RP tem um Algoritmo Las Vegas como o seguinte:

• Suponha que tenhamos uma linguagem L reconhecida ao mesmo tempo pelo algoritmo A RP e o (de possível diferente complexidade) algoritmo B co-RP.
• Dada uma entrada em L, execute A na entrada. Se retorna SIM, a resposta deve ser SIM.Do contrário execute B da entrada, a resposta deve ser NÃO. Se nada disto ocorrer retipe o passo.

Note que somente uma máquina pode dar a resposta errada, e a chance desta máquina dar a resposta errada durante cada execução é 50%. Isto significa que a chance de alcançar a kº rodada se reduz de forma expontencial a k, mostrando que o tempo esperado de execução é polinominal. Isto mostra que a interseção de co-RP com co-RP está contida em ZPP.

Para mostrar que ZPP está contido na interseção RP com co-RP, supomos que tenhamos um Algoritmo de Las Vegas C que resolva o problema. Podemos construir o seguinte algoritmo RP :

• Execute C ao menos pelo dobro do tempo esperado. Se ele der a resposta correta, dê esta resposta. Se ele não der a nenhuma resposta antes de interrrompermos, respondemos NÃO.

Pela Desigualdade de Markov, a chance de atingirmos a resposta antes de parar é 1/2. Isto significa que a chance de darmos a resposta errada numa questão de SIM, parando e informando NÃO, é apenas 1/2, batendo com a definição de algoritmo em RP. O algoritmo em co-RP é identico, exceto que fornece SIM se C não responde antes de ser interrompido.

Desde que ZPP=RP ∩ coRP, ZPP é obviamente contida em RP e coRP.

A classe P é contida em ZPP, e alguns cientistas de computação especulam que P=ZPP: i.e. todo Algoritmo de Las Vegas tem seu equivalente determinístico de tempo polinominal.

Fica em aberto quando ZPP = EXPTIME (ainda que quase certamente falso).O resultado P=ZPP pode provar o contrário, como P ≠ EXPTIME (veja Teorema hierarquico do tempo).

• Computação Probabilística

• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «ZPP (complexity)», especificamente desta versão.

• ZPP - from Complexity Zoo
• ZPP - Dicionário de algoritmos