Pequenos circuitos para problemas de avaliação de circuitos

Deixe- ser a função que mapeia um s circuito -gate C em n bits e um n cadeia de bits de . Suponha que os circuitos sejam codificados como uma sequência acíclica de atribuições onde são etiquetas de arame.$\mathsf{CircuitEval}_{s, n}$$s$$C$$n$$n$C ( x ) k : = g ( i , j ) i , j , $x$$C(x)$$k := g(i, j)$$i, j, k$

Sei que essa é uma pergunta meio engraçada, mas qual é o limite superior mais conhecido na complexidade do circuito desse problema? Existe uma TM única calcula essa função e, portanto, pela simulação Fischer-Pippenger, o tamanho O ( ( s + n ) 2 log ( s + n ) ) deve ser suficiente. O quadrático vem de ter que procurar para frente e para trás. É possível fazer melhor? É possível fazer no tamanho O ( s + n ) ?$O((s + n)^2)$$O((s + n)^2 \log(s + n))$$O(s + n)$

Aprendi conversando com Ryan Williams (que merece o crédito por eu poder postar esta resposta) que Paul e Pippenger sabem que o Circuit Eval pode ser decidido por um multitape TM de tempo quaseilinear e também que há reduções do multitape TMs para circuitos que fornecem apenas uma explosão de tamanho quase-linear. Ou seja, o Circuito Eval possui circuitos de tamanho , conforme sua formulação.$(n+s)\log^{O(1)}(n+s)$

Há uma prova disso aqui na página 6 (consulte o Teorema 3.1 (Folclore)).