Teorema hierarki untuk kedalaman sirkuit

11

Teorema hierarki macam apa yang ada untuk kedalaman rangkaian?

Pernyataan seperti

jika dan maka . $g(n) \in o(f(n))$ $f(n) \in n^{O(1)}$ $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(n^{O(1)}, f(n))$

cc.complexity-theory circuit-complexity hierarchy-theorems circuit-depth Kaveh
sumber

3

Tidak ada yang benar-benar. Kita tidak tahu apakah

{N C}^{1} = P / p o l y

$\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ !

Kristoffer Arnsfelt Hansen

@ Kristoffer, ya, itu benar, saya memberikannya sebagai contoh dari jenis pernyataan yang saya cari. Dengan kata lain kelas-kelas sirkuit yang menarik di mana kedalamannya diketahui membuat kelas lebih besar.

Kaveh

2

Saya tidak yakin, tetapi ini harus berhasil. Kita tahu bahwa kedalaman minimum suatu rangkaian untuk

f

$f$ adalah

\approx

$\approx$ logaritma dari ukuran minimum rumus untuk

f

$f$ . Sekarang, hierarki untuk ukuran rumus harus dimungkinkan untuk ditampilkan dengan cara yang sama seperti untuk ukuran sirkuit (menggunakan hasil Shannon-Lupanov). Katakanlah, sirkuit ukuran

4 t

$4t$ benar-benar lebih kuat dari sirkuit ukuran

t

$t$ . Tentu saja, hal-hal menjadi sedikit lebih rumit, jika kita membutuhkan ukuran polinomial.

Stasys

8

Sebuah makalah Klawe, Paul, Pippenger, dan Yannakakis memberikan teorema hierarki untuk formula monoton kedalaman konstan: http://dl.acm.org/citation.cfm?id=808717

Khususnya, untuk setiap memberikan fungsi yang dapat dihitung dengan rumus kedalaman dan ukuran tetapi membutuhkan formula kedalaman ukuran . $k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

Atau Meir
sumber

7

Raz dan McKenzie, dalam Pemisahan hierarki monoton NC , menunjukkan bahwa hierarki monoton NC ketat, dan memisahkan monoton NC dari monoton P.

Yuval Filmus
sumber

Teorema hierarki untuk kedalaman sirkuit

Jawaban: