Classe ZPP

16 maio 2011, 10:00 • José Félix Costa

Estudos sobre a classe ZPP: algoritmos de «Las Vegas».

Proposição: A classe ZPP está fechada para a complementação, união e intersecção.

Proposição: ZPP = R inters. co-R.

Proposição: P incl. ZPP incl. NP inters. co-NP.

Síntese das classes polinomiais.

Algoritmos Probabilísticos: Exercícios

11 maio 2011, 14:00 • José Félix Costa

Exercício: Mostre que

(a) P incl. R;

(b) P incl co-R;

(c) R incl. NP;

(d) co-R incl. co-NP;

(e) R incl. BPP;

(f) co-R incl. BPP.

Exercício: Mostre que as seguintes classes estão fechadas para a redução de muitos para um em tempo polinomial:

(a) PP;

(b) BPP;

(c) R;

(d) co-R.

Exercício: Mostre que se NP incl. BPP, então R = NP.

Classe R

10 maio 2011, 10:00 • José Félix Costa

Proposição: D^P incl. PP. [ D^P = {A inters. B: A in ^NP e B in co-NP}. ]

Proposição: A classe BPP está fechada para a complementação, união e intersecção.

A classe R.

Proposição: Um conjunto A está em R se e só se, para todo o polinómio p, existe uma máquina de Turing probabilística polinomial que decide A com probabilidade de erro de quanto muito (1/2)^p(|x|) para as palavras de A e rejeita todas as palavras de A.

Proposição: A classe R está fechada para a união e intersecção.

Proposição: A classe R pode ser redefinida mudando o critério de aceitação: a probalibidade de erro é qualquer valor 0 <= epsilon < 1, mantendo-se a probabilidade de erro 0 para palavras probabilisticamente rejeitadas.

Classe BPP

9 maio 2011, 10:00 • José Félix Costa

A classe BPP.

Proposição: Um conjunto A está em BPP se e só se, para todo o polinómio p, existe uma máquina de Turing probabilística polinomial que decide A com probabilidade de erro de quanto muito (1/2)^p(|x|).

Bijecções e equipotências

4 maio 2011, 14:00 • José Félix Costa

Exercício: Mostre, exibindo a respectiva bijecção, que os seguintes conjuntos são equipotentes:

(a) Os números naturais e os números inteiros;

(b) Os intervalos ]0,1] e ]0,1[;

(c) Os números reais e o intervalo ]0,1[;

(d) Os números reais e o intervalo ]0,1];

(e) Os números reais e o intervalo ]0,+\infty[;

(f) As palavras binárias e os números naturais;

(g) As linguagens binárias infinitas e o intervalo ]0,1];

(h) As linguagens binárias infinitas e os números reais.

Exercício: Mostre que, para qualquer conjunto A, A e P(A) não são equipotentes.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

TPC:

Exercício: Mostre, exibindo a respectiva bijecção, que os seguintes conjuntos são equipotentes:

(a) Os pares de números naturais e os números naturais (usando uma bijecção de grau não superior ao segundo);

(b) As sucessões de dígitos decimais e os números reais;

(c) As sequências binárias infinitas e os números reais.