Conselhos

25 maio 2011, 14:00 • José Félix 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 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 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 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 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|).

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