Upload
juliana-felix
View
1.166
Download
2
Embed Size (px)
DESCRIPTION
Apresentação desenvolvida para a disciplina de Teoria da Computação.Algoritmos de Aproximação e Algoritmos Probabilísticos.Juliana Paula Félix
Citation preview
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao e AlgoritmosProbabilısticos
Juliana Felix
28 de agosto de 2014
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
1 Motivacao
2 Algoritmos de Aproximacao
3 Algoritmos ProbabilısticosIntroducaoClasse BPPCLasse RP e co-RPCLasse ZPP
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
1 Motivacao
2 Algoritmos de Aproximacao
3 Algoritmos ProbabilısticosIntroducaoClasse BPPCLasse RP e co-RPCLasse ZPP
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
O Problema
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
O Problema
Obter um algoritmo polinomial para problemas NP-difıcilimplicaria que P=NP;
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
O Problema
Obter um algoritmo polinomial para problemas NP-difıcilimplicaria que P=NP;
Na pratica, algoritmos otimos podem nao ser necessarios,e pode-se buscar algoritmos aproximativos ouprobabilısticos.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
O Problema
Obter um algoritmo polinomial para problemas NP-difıcilimplicaria que P=NP;
Na pratica, algoritmos otimos podem nao ser necessarios,e pode-se buscar algoritmos aproximativos ouprobabilısticos.
Uma solucao quase otima e suficientemente boa quando emais facil de ser encontrada.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
1 Motivacao
2 Algoritmos de Aproximacao
3 Algoritmos ProbabilısticosIntroducaoClasse BPPCLasse RP e co-RPCLasse ZPP
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Um algoritmo de aproximacao e desenvolvido paraencontrar solucoes aproximadamente otimas;
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Um algoritmo de aproximacao e desenvolvido paraencontrar solucoes aproximadamente otimas;
Exemplo COB-VERT -MIN
Encontrar um algoritmo de tempo polinomial que produzuma cobertura de vertices de G que nunca e mais queduas vezes maior que uma menor cobertura de vertices.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Um algoritmo de aproximacao e desenvolvido paraencontrar solucoes aproximadamente otimas;
Exemplo COB-VERT -MIN
Encontrar um algoritmo de tempo polinomial que produzuma cobertura de vertices de G que nunca e mais queduas vezes maior que uma menor cobertura de vertices.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
A resolve aproximadamente COB-VERT -MIN em tempopolinomial
A =”Sobre a entrada < G >, onde G e um grafonao-direcionado:
1 Repita o seguinte ate que todas as arestas em G toquemuma aresta marcada:
2 Encontre uma aresta em G nao tocada por nenhumaaresta marcada.
3 Marque essa aresta.
4 De como saıda todos os nos que sao extremidade dearestas marcadas.”
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Prova
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Prova
A roda em tempo polinomial e o conjunto X dado comosaıda pelo algoritmo e uma cobertura, pois H (conjunto dearestas marcadas) contem (ou toca) todas as arestas emG . Logo, X toca todas em G .
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Prova
A roda em tempo polinomial e o conjunto X dado comosaıda pelo algoritmo e uma cobertura, pois H (conjunto dearestas marcadas) contem (ou toca) todas as arestas emG . Logo, X toca todas em G .
X e duas vezes tao grande quanto H, e Y (uma dasmenores coberturas em G ) e no mınimo tao grandequanto H.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Prova (cont.)
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Prova (cont.)
Y e uma cobertura. Logo, toda aresta em H toca um noem Y , e nenhum no de Y toca duas arestas em H, pois asmesmas nao se tocam.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Algoritmos de Aproximacao
Prova (cont.)
Y e uma cobertura. Logo, toda aresta em H toca um noem Y , e nenhum no de Y toca duas arestas em H, pois asmesmas nao se tocam.
Portanto, Y e no mınimo tao grande quanto H, pois Ypossui um no diferente que toca toda aresta em H. Porfim, X e no maximo duas vezes maior que Y .
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
1 Motivacao
2 Algoritmos de Aproximacao
3 Algoritmos ProbabilısticosIntroducaoClasse BPPCLasse RP e co-RPCLasse ZPP
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Introducao
Um algoritmo probabilıstico e um algoritmo concebidopara usar o resultado de um processo aleatorio.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Introducao
Um algoritmo probabilıstico e um algoritmo concebidopara usar o resultado de um processo aleatorio.
Problemas
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Introducao
Um algoritmo probabilıstico e um algoritmo concebidopara usar o resultado de um processo aleatorio.
Problemas
Calcular a melhor escolha pode requerer muito tempo,enquanto estimar o resultado pode ser suficiente;
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Introducao
Um algoritmo probabilıstico e um algoritmo concebidopara usar o resultado de um processo aleatorio.
Problemas
Calcular a melhor escolha pode requerer muito tempo,enquanto estimar o resultado pode ser suficiente;
Estimar o resultado pode resultar (espera-se que combaixa probabilidade) em solucoes erroneas.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Definicao
Definicao
Uma maquina de Turing probabilıstica(MTP) M e um tipode maquina de Turing nao-determinıstica na qual cada passonao-determinıstico e chamado de passo de
arremesso-de-moeda e tem dois movimentos seguinteslegıtimos.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Definicao
Definicao (cont.)
Atribuımos uma probabilidade a cada ramo b da computacaode M sobre a entrada w da seguinte forma. Defina aprobabilidade do ramo b como
Pr [b] = 2−k
onde k e o numero de passos de arremesso-de-moeda queocorrem no ramo b. Defina a probabilidade de que M aceita wcomo
Pr [M aceita w ] =∑
b e um ramo de aceitacao
Pr [b]
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Reconhecimento em MTP
Uma MTP M admite uma probabilidade de erro ε = 2−n,onde n e a entrada.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Reconhecimento em MTP
Uma MTP M admite uma probabilidade de erro ε = 2−n,onde n e a entrada.
Probabilidade de que M aceita w quando w ∈ L(M) e de:
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Reconhecimento em MTP
Uma MTP M admite uma probabilidade de erro ε = 2−n,onde n e a entrada.
Probabilidade de que M aceita w quando w ∈ L(M) e de:
1 w ∈ A implica Pr [M aceita w ] ≥ 1− ε, e
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Reconhecimento em MTP
Uma MTP M admite uma probabilidade de erro ε = 2−n,onde n e a entrada.
Probabilidade de que M aceita w quando w ∈ L(M) e de:
1 w ∈ A implica Pr [M aceita w ] ≥ 1− ε, e
2 w /∈ A implica Pr [M rejeita w ] ≥ 1− ε.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe BPP (Bounded-error probabilisticpolynomial)
Definicao
BPP e a classe de linguagens reconhecidas por maquinas deTuring probabilısticas de tempo polinomial com umaprobabilidade de erro de 1
3 .Algoritmos que reconhecem linguagens em BPP sao chamadosde Atlantic city.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe BPP (Bounded-error probabilisticpolynomial)
Definicao
BPP e a classe de linguagens reconhecidas por maquinas deTuring probabilısticas de tempo polinomial com umaprobabilidade de erro de 1
3 .Algoritmos que reconhecem linguagens em BPP sao chamadosde Atlantic city.
Uma definicao semelhante poderia ser feita para umaprobabilidade de erro entre 0 e 1
2 , em virtude do lema da
amplificacao que oferece uma maneira simples de tornara probabilidade de erro exponencialmente pequena.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Lema
Seja ε uma constante fixa estritamente entre 0 e 12 . Entao,
para qualquer polinomio poly(n), uma maquina de Turingprobabilıstica de tempo polinomial M1 que opera comprobabilidade de erro ε tem uma maquina de Turingprobabilıstica de tempo polinomial equivalente M2 que operacom uma probabilidade de erro de 2−poly(n).
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Ideia da Prova
M2 simula M1 rodando-a um numero polinomial de vezes etomando o voto da maioria dos resultados. A probabilidade deerro decresce exponencialmente com o numero de execucoes deM1 realizadas.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Dada a MT M1 que reconhece uma linguagem com umaprobabilidade de erro ǫ < 1
2 e um polinomio poly(n),construımos uma MT M2 que reconhece a mesmalinguagem com uma probabilidade de erro de 2−poly(n).
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Dada a MT M1 que reconhece uma linguagem com umaprobabilidade de erro ǫ < 1
2 e um polinomio poly(n),construımos uma MT M2 que reconhece a mesmalinguagem com uma probabilidade de erro de 2−poly(n).
Prova
M2 = ”Sobre a entrada w :
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Dada a MT M1 que reconhece uma linguagem com umaprobabilidade de erro ǫ < 1
2 e um polinomio poly(n),construımos uma MT M2 que reconhece a mesmalinguagem com uma probabilidade de erro de 2−poly(n).
Prova
M2 = ”Sobre a entrada w :
Calcule k
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Dada a MT M1 que reconhece uma linguagem com umaprobabilidade de erro ǫ < 1
2 e um polinomio poly(n),construımos uma MT M2 que reconhece a mesmalinguagem com uma probabilidade de erro de 2−poly(n).
Prova
M2 = ”Sobre a entrada w :
Calcule k
Rode 2k simulacoes independentes de M1 sobre a entradaw .
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Dada a MT M1 que reconhece uma linguagem com umaprobabilidade de erro ǫ < 1
2 e um polinomio poly(n),construımos uma MT M2 que reconhece a mesmalinguagem com uma probabilidade de erro de 2−poly(n).
Prova
M2 = ”Sobre a entrada w :
Calcule k
Rode 2k simulacoes independentes de M1 sobre a entradaw .
Se a maioria das execucoes de M1 aceita, entao aceite;caso contrario, rejeite.”
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
O estagio 2 da uma sequencia de 2k resultados dasimulacao de M1.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
O estagio 2 da uma sequencia de 2k resultados dasimulacao de M1.
Cada resultado pode ser certo (c) ou errado (e).
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
O estagio 2 da uma sequencia de 2k resultados dasimulacao de M1.
Cada resultado pode ser certo (c) ou errado (e).
S a sequencia de resultados obtidos no estagio 2.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
O estagio 2 da uma sequencia de 2k resultados dasimulacao de M1.
Cada resultado pode ser certo (c) ou errado (e).
S a sequencia de resultados obtidos no estagio 2.
S contem 2k resultados, onde 2k = c + e.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
O estagio 2 da uma sequencia de 2k resultados dasimulacao de M1.
Cada resultado pode ser certo (c) ou errado (e).
S a sequencia de resultados obtidos no estagio 2.
S contem 2k resultados, onde 2k = c + e.
Se c ≤ e entao M2 da uma resposta incorreta (S edenominada uma sequencia ruim).
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
Se S e uma sequencia ruim, entao PS ≤ ǫe(1− ǫ)c
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
Se S e uma sequencia ruim, entao PS ≤ ǫe(1− ǫ)c
ǫe(1− ǫ)c = ǫk(1− ǫ)k , porque k ≤ e e ǫ < 1− ǫ.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
Se S e uma sequencia ruim, entao PS ≤ ǫe(1− ǫ)c
ǫe(1− ǫ)c = ǫk(1− ǫ)k , porque k ≤ e e ǫ < 1− ǫ.
A somatoria de todas as sequencias ruins da aprobabilidade de que M2 gere uma saıda incorreta:
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
Se S e uma sequencia ruim, entao PS ≤ ǫe(1− ǫ)c
ǫe(1− ǫ)c = ǫk(1− ǫ)k , porque k ≤ e e ǫ < 1− ǫ.
A somatoria de todas as sequencias ruins da aprobabilidade de que M2 gere uma saıda incorreta:
∑
S ruim
PS ≤ 22k .ǫk(1− ǫ)k = (4ǫ(1− ǫ))k
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Lema da Amplificacao
Prova (cont.)
Se S e uma sequencia ruim, entao PS ≤ ǫe(1− ǫ)c
ǫe(1− ǫ)c = ǫk(1− ǫ)k , porque k ≤ e e ǫ < 1− ǫ.
A somatoria de todas as sequencias ruins da aprobabilidade de que M2 gere uma saıda incorreta:
∑
S ruim
PS ≤ 22k .ǫk(1− ǫ)k = (4ǫ(1− ǫ))k
Como ǫ < 12 , portanto 4ǫ(1− ǫ) < 1 e, consequentemente,
a probabilidade anterior decresce exponencialmente em k.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Teorema (pequeno teorema de Fermat)
Se p e primo e a ∈ Z+p , entao ap−1 ≡ 1 (mod p)
Teste de Primalidade
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Teorema (pequeno teorema de Fermat)
Se p e primo e a ∈ Z+p , entao ap−1 ≡ 1 (mod p)
Teste de Primalidade
2(7−1) = 26 = 64 ≡ 1 (mod 7)
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Teorema (pequeno teorema de Fermat)
Se p e primo e a ∈ Z+p , entao ap−1 ≡ 1 (mod p)
Teste de Primalidade
2(7−1) = 26 = 64 ≡ 1 (mod 7)
2(6−1) = 25 = 32 ≡ 2 (mod 6)
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Erros do Teste de Primalidade
2(341−1) ≡ 1 (mod 341)
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Erros do Teste de Primalidade
2(341−1) ≡ 1 (mod 341)
11 ∗ 31 = 341.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Erros do Teste de Primalidade
2(341−1) ≡ 1 (mod 341)
11 ∗ 31 = 341.
Numeros pseudoprimos sao aqueles que passam no testede Fermat para todo a menor que ele, e primo em relacaoa ele.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Erros do Teste de Primalidade
2(341−1) ≡ 1 (mod 341)
11 ∗ 31 = 341.
Numeros pseudoprimos sao aqueles que passam no testede Fermat para todo a menor que ele, e primo em relacaoa ele.
Numeros de Carmichael: numeros compostos que aindaassim passam no teste de Fermat.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
PSEUDOPRIMO = ”Sobre a entrada p, faca:
1 Selecione a1, ...., ak aleatoriamente em Z+p .
2 Compute ap−1i mod p para cada i .
3 Se todos os valores computados forem 1, aceite. Casocontrario, rejeite.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Se p for primo, ele passa em todos os teste e o algoritmoaceita com certeza.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Se p for primo, ele passa em todos os teste e o algoritmoaceita com certeza.
Se p nao for pseudoprimo, ele passa em, no maximo,metade de todos os testes.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Se p for primo, ele passa em todos os teste e o algoritmoaceita com certeza.
Se p nao for pseudoprimo, ele passa em, no maximo,metade de todos os testes.
Nesse caso, ele passa em cada teste com probabilidade deno maximo 1
2 e, portanto, a probabilidade de que ele passeem todos os k testes aleatoriamente selecionados e, nomaximo, 2−k .
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Primalidade
Se p for primo, ele passa em todos os teste e o algoritmoaceita com certeza.
Se p nao for pseudoprimo, ele passa em, no maximo,metade de todos os testes.
Nesse caso, ele passa em cada teste com probabilidade deno maximo 1
2 e, portanto, a probabilidade de que ele passeem todos os k testes aleatoriamente selecionados e, nomaximo, 2−k .
O algoritmo opera em tempo polinomial porque aexponenciacao modular e computavel em tempopolinomial (cap. 7).
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe RP (Randomized Polynomial time)
Definicao
RP e a classe de linguagens que sao reconhecidas por maquinasde Turing probabilısticas de tempo polinomial em que entradasna linguagem sao aceitas com uma probabilidade de, nomınimo, 1
2 e entradas que nao estao na linguagem saorejeitadas com uma probabilidade de 1.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe RP (Randomized Polynomial time)
Simplificando
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe RP (Randomized Polynomial time)
Simplificando
Se a resposta correta e:
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe RP (Randomized Polynomial time)
Simplificando
Se a resposta correta e:
nao, sempre retorna nao.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe RP (Randomized Polynomial time)
Simplificando
Se a resposta correta e:
nao, sempre retorna nao.sim, retorna sim com probabilidade de erro de 1
2
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe co-RP
Classe co-RP
Se a resposta correta e:
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe co-RP
Classe co-RP
Se a resposta correta e:
sim, sempre retorna sim.nao, retorna nao com probabilidade de erro 1
2 .
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe co-RP
Classe co-RP
Se a resposta correta e:
sim, sempre retorna sim.nao, retorna nao com probabilidade de erro 1
2 .
Algoritmos que reconhecem linguagens em RP , ou co-RPsao conhecidos como Monte-Carlo.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Definicao
ZPP e a classe de linguagens que uma MTP para em tempopolinomial, sem falsas aceitacoes ou rejeicoes, mas as vezes daum nao sei como resposta. ZPP e = a RP ∩ co-RP .Conhecido como algoritmo de Las Vegas.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Simplificando
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Simplificando
Sempre retorna uma resposta sim ou nao.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Simplificando
Sempre retorna uma resposta sim ou nao.
Pode retornar um nao sei como resposta.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Prova: RP ∩ co-RP ⊆ ZPP
Seja L uma linguagem, T seu decisor em RP e B o decisor emco-RP . A seguinte MT M decide L em ZPP .M = ”Sobre a entrada w , faca:
1 Rode T sobre w . Se T aceita, aceite.
2 Rode B sobre w . Se T rejeita, rejeite.
3 Em outros casos, de como saıda ”Nao sei. E melhor rodara entrada novamente”.”
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Prova
Como T e B rodam em tempo polinomial, M tambemroda em tempo polinomial. Pelas definicoes de RP eco-RP , temos que:
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Prova
Como T e B rodam em tempo polinomial, M tambemroda em tempo polinomial. Pelas definicoes de RP eco-RP , temos que:
Se T aceita w , entao w ∈ L.
Se B rejeita w , entao w /∈ L.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Prova
Como T e B rodam em tempo polinomial, M tambemroda em tempo polinomial. Pelas definicoes de RP eco-RP , temos que:
Se T aceita w , entao w ∈ L.
Se B rejeita w , entao w /∈ L.
M pode ser executado por um numero k de vezes, econforme k aumenta, a probabilidade de M responder naosei diminui.
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Classe ZPP (Zero-error Probabilistic Polinomial)
Prova: ZPP ⊆ RP
Seja C um algoritmo de Las Vegas.
Rode C sobre w . Se C da uma resposta, de essa resposta.
Se C responde nao sei, entao rejeite.
ZPP ⊆ co-RP e feita de forma similar, trocando nao seipor aceite.
ZPP ⊆ RP ∩ co-RP e RP ∩ co-RP ⊆ ZPP
ZPP = RP ∩ co-RP
Algoritmos deAproximacaoe AlgoritmosProbabilısticos
Juliana Felix
Motivacao
Algoritmos deAproximacao
AlgoritmosProbabilısticos
Introducao
Classe BPP
CLasse RP eco-RP
CLasse ZPP
Bibliografia
Referencia Bibliografica
Sipser, Michael(2006). Introduction To Theory ofComputation. Thompson Course Technology.