Pengurangan kedalaman untuk sirkuit Boolean

Hasil ini oleh Tavenas, Koiran dan lain-lain menunjukkan bahwa setiap polinomial yang dihitung oleh sirkuit ukuran $s$ dihitung oleh kedalaman-4 sirkuit homogen ukuran $s^{\sqrt{d}}$ .

Apakah ada hasil yang serupa untuk sirkuit Boolean atau kita tahu mengapa hal seperti itu tidak mungkin?

cc.complexity-theory circuit-complexity arithmetic-circuits Pelajar Matematika
sumber

Jika saya ingat dengan benar, hasil seperti itu tidak mungkin terjadi di dunia boolean. Saya mengalami kesulitan mengingat hasil tertentu, saya pikir mungkin ini arxiv.org/abs/1504.03398 poin ke arah ini. Saya dapat memperbarui ini ke jawaban jika saya menemukan referensi yang sebenarnya saya ingat samar-samar.

chazisop

Jawaban:

$O(n)$ $O(\log{n})$ $2^{O(n/\log\log{n})}$

$\Theta(2^{n/2})$ $2^{\Omega(\sqrt{n})}$

Alex Golovnev
sumber

{A C C}^{0}

$\mathsf{ACC}^0$

d

$d$

2

$2$

2^{p o l y l o g (n)}

$2^{polylog(n)}$

p o l y l o g (n)

$polylog(n)$