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.