Sumários

Conselhos

25 Maio 2011, 14:00 José Félix Gomes da Costa

Exercício: Mostre que P/PF = P.

Exercício: Mostre que (co-C)/F = co-(C/F).

Exercício: Mostre que P/poly/poly = P/poly.

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

TPC:

Mostre que BPP tem circuitos polinomiais.

Mostre que ZPP tem circuitos polinomiais.

Mostre que R tem circuitos polinomiais.

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

Nota:

As notas do meu livro encontram-se aqui.

 


Circuitos

24 Maio 2011, 10:00 José Félix Gomes da Costa

Sequência de computação. Conceito de função booleana computável por uma sequência de computação.
Circuito booleano.

Custo ou tamanho de um circuito. Profundidade de um circuito. Exemplo: Produto interno de dois vectores booleanos.

Codificação de circuitos booleanos (em tempo polinomial). 

Famílias de circuitos e funções associadas custo e profundidade.

Proposição: Se A é um conjunto decidível por uma máquina de Turing M em tempo t, então a família de circuitos que simula M tem custo c_A(n) in O(t(n)^2).

Circuitos de tamanho polinomial.

O problema CVP.

Proposição: CVP in P.

Proposição: Um conjunto A tem circuitos de tamanho polinomial se e só se A in P/poly.

 


Conselhos

23 Maio 2011, 10:00 José Félix Gomes da Costa

Conselhos

Classes de complexidade definidas à custa de classes de conselhos: classes não uniformes C/F.

P/log,  P/poly, PSPACE/poly.

Versões de HALT e SAT em P/poly.

Proposição: Se SAT está em P/log, então P = NP.


 


Algoritmos Probabilísticos: Exercícios

18 Maio 2011, 14:00 José Félix Gomes da Costa

Exercício: Mostre que se A é decidível por uma máquina de Turing probabilística polinomial de três outputs, com probabilidade de erro 0 e probabilidade epsilon < 1 de não dar resposta, então A está em ZPP.

Exercício: Mostre que a classe ZPP está fechada para a complementação, intersecção e união.

Exercício: Mostre que as classes BPP, R e ZPP são fechadas para a redução-m.



 


Conselhos

17 Maio 2011, 10:00 José Félix Gomes da Costa

Construção das classes probabilísticas por conselhos

Conselhos, conselhos correctos para um conjunto. Conselhos pequenos.

Proposição: As asserções seguintes são equivalentes: (a) A está em BPP, (b) Para todo o polinómio q, há um conjunto B em P e um polinómio p tais que, entre as palavras de tamanho p(n), existem pelo menos 2^p(n) ( 1 - (1/2)^q(n) ) conselhos correctos para A, para palavras de tamanho n.

Proposição: Mostre que um conjunto A está em PP se e só se existe um conjunto Q em P e um polinómio p, tais que (a) se x in A então <x,y> in Q para mais de 1/2 das palavras y tais que |y| = p(|x|) e (b) se x not in A então <x,y> not in Q para mais de 1/2 das palavras y tais que |y| = p(|x|).

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

TPC

Exercício: Mostre que um conjunto A está em PP se e só se existe um conjunto Q em P e um polinómio p, tais que (a) se x in A então <x,y> in Q para mais de 1/2 das palavras y tais que |y| <= p(|x|) e (b) se x not in A então <x,y> not in Q para mais de 1/2 das palavras y tais que |y| <= p(|x|).

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