Małe obwody dla problemu oceny obwodu

Niech jest funkcją, która odwzorowuje s -gate obwód C w n bitów i jest n -bitowy ciąg X do C ( X ) . Załóżmy, że obwody są kodowane jako acykliczna sekwencja przypisań k : = g ( i , j ), gdzie i , j , k są etykietami przewodowymi.$\mathsf{CircuitEval}_{s, n}$$s$$C$$n$$n$$x$$C(x)$$k := g(i, j)$$i, j, k$

Wiem, że to trochę zabawne pytanie, ale jaka jest najbardziej znana górna granica złożoności obwodu tego problemu? Istnieje taśma TM z pojedynczą taśmą oblicza tę funkcję, a zatem dzięki symulacji Fischera-Pippengera rozmiar O ( ( s + n ) 2 log ( s + n ) ) powinien wystarczyć. Kwadrat pochodzi z konieczności szukania tam iz powrotem. Czy można to zrobić lepiej? Czy można to zrobić w rozmiarze O ( s + n ) ?$O((s + n)^2)$$O((s + n)^2 \log(s + n))$$O(s + n)$

Nauczyłem się od rozmowy z Ryanem Williamsem (który zasługuje na uznanie za to, że mogłem opublikować tę odpowiedź), że od Paula i Pippengera wiadomo, że o Circuit Eval można zadecydować za pomocą quasilinear czasu multitape TM, a także, że istnieją ograniczenia z multitape TM do obwodów, które powodują jedynie powiększenie quasi-liniowe. To znaczy, Circuit Eval ma obwody o rozmiarze , zgodnie z twoją formułą.$(n+s)\log^{O(1)}(n+s)$

Jest tego dowód tutaj na stronie 6 (patrz Twierdzenie 3.1 (Folklor)).