ZPP
 | Este artigo não cita fontes confiáveis. (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.
Definição de interseção
[editar | editar código-fonte]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.
Coneções com outras classes
[editar | editar código-fonte]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).
Ver também
[editar | editar código-fonte]Notas
- 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.