Małe obwody dla problemu oceny obwodu

14

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.CircuitEvals,nsCnnxC(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)2log(s+n))O(s+n)

Izaak Meckler
źródło

Odpowiedzi:

16

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)logO(1)(n+s)

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

Dylan McKay
źródło
To jest idealne, dzięki! I dzięki Ryanowi!
Izaak Meckler,