Kleine Schaltkreise für Schaltkreisauswertungsproblem

Es sei die Funktion, die eine Gate-Schaltung auf Bits und eine Bit-Zeichenfolge auf abbildet . Es sei angenommen, dass Schaltungen als eine azyklische Folge von Zuweisungen codiert sind, wobei sind. sCnnxC(x)k:=g(i,j)i,j,$\mathsf{CircuitEval}_{s, n}$$s$$C$$n$$n$$x$$C(x)$$k := g(i, j)$$i, j, k$

Ich weiß, dass dies eine witzige Frage ist, aber was ist die bekannteste Obergrenze für die Schaltungskomplexität dieses Problems? Es gibt ein Single-Tape TM, das diese Funktion berechnet, und so sollte nach der Fischer-Pippenger-Simulation Größe ausreichen . Das Quadrat entsteht, wenn man hin und her suchen muss. Kann man es besser machen? Ist es möglich, in Größe zu tun ?O ( ( s + n ) 2 log ( s + n ) ) O ( s + n $O((s + n)^2)$$O((s + n)^2 \log(s + n))$$O(s + n)$

Ich habe aus Gesprächen mit Ryan Williams (dem es zu verdanken ist, dass ich diese Antwort posten konnte) erfahren, dass Paul und Pippenger wissen, dass Circuit Eval durch ein quasilineares Zeit-Multitape TM entschieden werden kann und dass es Reduzierungen durch Multitape gibt TMs für Schaltkreise, die nur eine quasilineare Vergrößerung ergeben. Das heißt, Circuit Eval hat gemäß Ihrer Formulierung Schaltkreise der Größe .$(n+s)\log^{O(1)}(n+s)$

Einen Beweis dafür finden Sie hier auf Seite 6 (siehe Satz 3.1 (Folklore)).