PP e BPP em conselhos

8 junho 2010, 14:00 • José Félix Costa

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 x in A se e só se (x,y) in Q para mais de 1/2 das palavras y tais que |y| = p(|x|).
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 x in A se e só se (x,y) in Q para mais de 1/2 das palavras y tais que |y| <= p(|x|).
Exercício : Mostre que um conjunto A está em BPP se e só se existe um conjunto Q em P e um polinómio p, tais que x in A se e só se (x,y) in Q para mais de 3/4 das palavras y tais que |y| = p(|x|).
Exercício : Mostre que um conjunto A está em BPP se e só se existe um conjunto Q em P e um polinómio p, tais que x in A se e só se (x,y) in Q para mais de 3/4 das palavras y tais que |y| <= p(|x|).

Teorema de Lupanov

8 junho 2010, 12:30 • José Félix Costa

Limite superior da complexidade de uma função booleana n-ária: 2^n - 4.
Proposição : Todo o conjunto é decidível por circuitos exponenciais.
Teorema de Lupanov : O custo de uma função booleana n-ária f é c(f) = 1/n (1 + O(n^(-1/2))) 2^n.
Proposição : A fracção de funções booleanas n-árias com custo majorado por g(n) > n + 2 é majorado por F_g(n) < 1/n (12 e g(n))^g(n) 2^(-2^n).
Proposição : Se g(n) = (1 - \epsilon) 2^n / n, 0 < \epsilon < 1, então lim F_g(n) = 0.
Proposição : A fracção das funções booleanas n-árias com custo inferior a g(n) = (1 - \epsilon) 2^n / n, 0 < \epsilon < 1, é diminuta para grandes valores de n.

Redução em espaço logarítmico

4 junho 2010, 16:00 • José Félix Costa

Problemas NLOG-completos: REACHABILITY.

Problemas P-completos: CVP.

P/poly não contém todos os conjuntos

4 junho 2010, 14:30 • José Félix Costa

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

Proposição : Existem conjuntos em EXPSPACE que não estão em P/poly.

Circuitos polinomiais

2 junho 2010, 14:00 • José Félix Costa

Proposição : P/poly = UNIÃO {S esparso} P(S).
Proposição : BPP tem circuitos polinomiais.
Proposição : R tem circuitos polinomiais.
Proposição : ZPP tem circuitos polinomiais.