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.

Definição de interseção

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

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

Notas

Ligações externas

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