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.