80
Algoritmos de Aproxima¸c˜ ao e Algoritmos Probabil´ ısticos Juliana F´ elix Motiva¸c˜ ao Algoritmos de Aproxima¸c˜ ao Algoritmos Probabil´ ısticos Introdu¸ ao Classe BPP CLasse RP e co-RP CLasse ZPP Bibliografia Algoritmos de Aproxima¸ ao e Algoritmos Probabil´ ısticos Juliana F´ elix 28 de agosto de 2014

Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 1: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 2: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 3: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 4: Algoritmos de Aproximação e Algoritmos Probabilísticos

Algoritmos deAproximacaoe AlgoritmosProbabilısticos

Juliana Felix

Motivacao

Algoritmos deAproximacao

AlgoritmosProbabilısticos

Introducao

Classe BPP

CLasse RP eco-RP

CLasse ZPP

Bibliografia

O Problema

Page 5: Algoritmos de Aproximação e Algoritmos Probabilí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;

Page 6: Algoritmos de Aproximação e Algoritmos Probabilí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.

Page 7: Algoritmos de Aproximação e Algoritmos Probabilí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.

Page 8: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 9: Algoritmos de Aproximação e Algoritmos Probabilísticos

Algoritmos deAproximacaoe AlgoritmosProbabilısticos

Juliana Felix

Motivacao

Algoritmos deAproximacao

AlgoritmosProbabilısticos

Introducao

Classe BPP

CLasse RP eco-RP

CLasse ZPP

Bibliografia

Algoritmos de Aproximacao

Page 10: Algoritmos de Aproximação e Algoritmos Probabilísticos

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;

Page 11: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 12: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 13: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.”

Page 14: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 15: Algoritmos de Aproximação e Algoritmos Probabilísticos

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 .

Page 16: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 17: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.)

Page 18: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 19: Algoritmos de Aproximação e Algoritmos Probabilísticos

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 .

Page 20: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 21: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 22: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 23: Algoritmos de Aproximação e Algoritmos Probabilísticos

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;

Page 24: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 25: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 26: Algoritmos de Aproximação e Algoritmos Probabilísticos

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]

Page 27: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 28: Algoritmos de Aproximação e Algoritmos Probabilísticos

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:

Page 29: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 30: Algoritmos de Aproximação e Algoritmos Probabilísticos

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− ε.

Page 31: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 32: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 33: Algoritmos de Aproximação e Algoritmos Probabilísticos

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).

Page 34: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 35: Algoritmos de Aproximação e Algoritmos Probabilísticos

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).

Page 36: Algoritmos de Aproximação e Algoritmos Probabilísticos

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 :

Page 37: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 38: Algoritmos de Aproximação e Algoritmos Probabilísticos

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 .

Page 39: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.”

Page 40: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.)

Page 41: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 42: Algoritmos de Aproximação e Algoritmos Probabilísticos

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).

Page 43: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 44: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 45: Algoritmos de Aproximação e Algoritmos Probabilísticos

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).

Page 46: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 47: Algoritmos de Aproximação e Algoritmos Probabilísticos

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− ǫ.

Page 48: Algoritmos de Aproximação e Algoritmos Probabilísticos

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:

Page 49: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 50: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 51: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 52: Algoritmos de Aproximação e Algoritmos Probabilísticos

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)

Page 53: Algoritmos de Aproximação e Algoritmos Probabilísticos

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)

Page 54: Algoritmos de Aproximação e Algoritmos Probabilísticos

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)

Page 55: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 56: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 57: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 58: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 59: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 60: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 61: Algoritmos de Aproximação e Algoritmos Probabilísticos

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 .

Page 62: Algoritmos de Aproximação e Algoritmos Probabilísticos

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).

Page 63: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 64: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 65: Algoritmos de Aproximação e Algoritmos Probabilísticos

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:

Page 66: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 67: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 68: Algoritmos de Aproximação e Algoritmos Probabilísticos

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:

Page 69: Algoritmos de Aproximação e Algoritmos Probabilísticos

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 .

Page 70: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 71: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 72: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 73: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 74: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 75: Algoritmos de Aproximação e Algoritmos Probabilísticos

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”.”

Page 76: Algoritmos de Aproximação e Algoritmos Probabilísticos

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:

Page 77: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 78: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.

Page 79: Algoritmos de Aproximação e Algoritmos Probabilísticos

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

Page 80: Algoritmos de Aproximação e Algoritmos Probabilísticos

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.