Sea la función que mapea un circuito -gate en bits y una cadena -bit a . Suponga que los circuitos están codificados como una secuencia acíclica de asignaciones donde son etiquetas de cable.
Sé que esta es una pregunta un poco extraña, pero ¿cuál es el límite superior más conocido en la complejidad del circuito de este problema? Hay una TM de una sola cinta que computa esta función, por lo que según la simulación Fischer-Pippenger, el tamaño debería ser suficiente . Lo cuadrático viene de tener que buscar de un lado a otro. ¿Es posible hacerlo mejor? ¿Es posible hacerlo en tamaño ?
fuente