Sirkuit kecil untuk masalah evaluasi sirkuit

Biarkan menjadi fungsi yang memetakan sirkuit gerbang pada bit dan string bit ke . Asumsikan bahwa sirkuit dikodekan sebagai urutan asiklik dari penugasan mana adalah label kawat. 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$

Saya tahu ini sedikit pertanyaan lucu, tapi apa batas atas yang paling dikenal pada kompleksitas masalah ini? Ada single-tape TM menghitung fungsi ini, dan oleh simulasi Fischer-Pippenger, ukuran harus cukup . Kuadrat berasal dari keharusan mencari bolak-balik. Apakah mungkin melakukan lebih baik? Apakah mungkin dilakukan dalam ukuran ?O ( ( s + n ) 2 log ( s + n ) ) O ( s + n $O((s + n)^2)$$O((s + n)^2 \log(s + n))$$O(s + n)$

Saya telah belajar dari berbicara dengan Ryan Williams (yang pantas mendapatkan pujian karena saya dapat memposting jawaban ini) bahwa diketahui dari Paul dan Pippenger bahwa Circuit Eval dapat diputuskan dengan waktu multitape TM waktu quasilinear dan juga ada pengurangan dari multitape TM ke sirkuit yang hanya memberikan blowup ukuran quasilinear. Yaitu, Circuit Eval memiliki sirkuit ukuran , sesuai formulasi Anda.$(n+s)\log^{O(1)}(n+s)$

Ada buktinya di sini di halaman 6 (lihat Teorema 3.1 (Cerita Rakyat)).