Algoritmos Probabilísticos, Parte 4: Classes de Complexidade
--
Algoritmos Probabilísticos são formalizados por Máquinas de Turing Probabilísticas. Uma Máquina de Turing Probabilística é uma Máquina de Turing Determinística, mas que possui acesso a uma fonte de aleatoriedade. A uso de um modelo de computação diferente leva a classes de complexidade próprias para Algoritmos Probabilísticos.
A classe PP (Probabilistic Polynomial Time), como o nome indica, é a equivalente da classe P para algoritmos probabilísticos: um problema pertence a classe PP se existe uma Máquina de Turing Probabilística que fornece uma solução para qualquer instância do problema em tempo polinomial com probabilidade de erro menor que 1/2 — isto é, se o algoritmo responder SIM, a resposta é NÃO com probabilidade menor que 1/2, e vice-versa. Esta probabilidade pode depender do tamanho da entrada.
Naturalmente, P ⊂ PP pois basta a Máquina de Turing Probabilística não utilizar a fonte de aleatoriedade para se tornar Determinística. NP também está em PP, pois é possível construir um algoritmo probabilístico que soluciona SAT (que sabemos ser NP-Completo). Isso não deve ser compreendido como “máquinas probabilísticas são mais capazes que não-determinísticas”, pois a classe PP exige muito pouco das soluções — basta que tenham uma probabilidade pouca coisa maior do que completamente aleatória de retornar uma decisão correta, seja para SIM ou NÃO. De fato, o algoritmo probabilístico para SAT exigiria uma quantidade de execuções exponenciais para obter algum tipo de resposta útil.
A classe BPP (Bounded-Error Probabilistic Polynomial Time) coloca limites mais estritos nos erros, de forma que se um problema pertence a classe BPP, então há uma solução eficaz na forma de um algoritmo probabilístico. Um problema pertence a BPP se a probabilidade de erro na resposta é no máximo 1/3 (este valor é arbitrário e pode ser alterado, desde que menor ou igual a 1/2). Esta probabilidade não pode depender do tamanho da entrada. Esta última exigência é a que distingue BPP da classe PP e permite que se reduza o erro exponencialmente executando o algoritmo múltiplas vezes.
Problemas em BPP possuem algoritmos de Monte Carlo eficientes para solucioná-los.
Sabe-se que P está contido em BPP, mas há problemas em BPP que não se sabe se estão em P. No entanto, acredita-se que P=BPP principalmente devido ao fato de ter-se encontrado ao longo dos anos algoritmos determinísticos eficientes para muitos problemas BPP. A relação entre BPP e NP não é bem conhecida, mas acredita-se que NP não está contida em BPP — do contrário, haveria algoritmos probabilísticos eficientes para solucionar problemas NP-Completos, mas nenhum é conhecido.
A classe RP (Randomized Polynomial Time) é um sub-conjunto da BPP. Um problema pertence a RP se existe uma Máquina de Turing Probabilística que executa em tempo polinomial e que (i) se a resposta para uma instância for NÃO, então o algoritmo sempre retorna NÃO; (ii) se a resposta for SIM, então o algoritmo retorna SIM com probabilidade de pelo menos 1/2 (e NÃO caso contrário). Isto é, a classe RP contém problemas que possuem algoritmos Monte Carlo com viés para NÃO.
Já a classe co-RP inverte a exigência, sempre retornando SIM quando a resposta for SIM, enquanto quando a resposta for NÃO a resposta possui uma probabilidade de estar errada. Os problemas em co-RP possuem algoritmos Monte Carlo com viés para SIM.
Tanto RP como co-RP estão contidos em BPP. P está contido na intersecção de RP e co-RP. Se for provado que BPP=P, então todas estas classes são a mesma.
Por fim, a classe ZPP (Zero-error Probabilistic Polynomial Time) contém problemas para os quais existe uma Máquina de Turing Probabilística que sempre retorna a solução correta em tempo médio polinomial. É, portanto, a classe de problemas para os quais existe um algoritmo Las Vegas que os soluciona.
ZPP é exatamente a interseção entre RP e co-RP. P está contido em ZPP e é possível que estas duas sejam iguais.
Conjectura-se que o gráfico abaixo representa a relação entre estas classes probabilísticas.
Incluindo as classes P, NP, NPC e co-NP:
