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.