PARITY

adalah kelas konstan mendalam sirkuit polinomial-ukuran dengan TIDAK gerbang dan tak terbatas fan-in AND dan gerbang OR, di mana input dan gerbang juga memiliki fanout tak terbatas. $AC^0$

Sekarang pertimbangkan sebuah kelas baru, sebut saja yang seperti tetapi input dan gatesnya paling banyak . Kelas ini jelas dalam . Bahkan, itu benar-benar terkandung dalam , seperti yang disebutkan di sini . Oleh karena itu, PARITY jelas tidak dalam . $AC^0_{bf}$ $AC^0$ $O(1)$ $AC^0$ $AC^0$ $AC^0_{bf}$

Apakah ada bukti PARITY yang tidak berlaku juga untuk ? Dengan kata lain, adakah bukti yang tidak menggunakan teknik yang kuat seperti pergantian lemma atau metode Razborov / Smolensky? $\notin AC^0_{bf}$ $AC^0$

cc.complexity-theory circuit-complexity Adam Paetznick
sumber

Ini disebut

dalam literatur: qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0

{N C}^{0}

$\mathsf{NC}^0$

Hsien-Chih Chang 張顯之

Tidak, karena fanin tidak terikat.

domotorp

Ah, saya salah membaca kata fanout. Terima kasih telah menunjukkan.

Hsien-Chih Chang 張顯之

Posting terkait oleh @Kaveh: cstheory.stackexchange.com/q/1824/1800 , dipindahkan dari komentar di bawah ini untuk meningkatkan paparan.

Hsien-Chih Chang 張顯之

Ngomong-ngomong, apa itu 'fanout terbatas'?

xxx ---

Jawaban:

Saya mungkin melewatkan sesuatu, tetapi bukankah sama dengan Formula? Karena setiap bit input dapat memiliki efek pada paling banyak jumlah gerbang yang terbatas, kita dapat dengan mudah mengira bahwa setiap gerbang hanya memiliki satu output (setelah mungkin menduplikasi beberapa hal) dan kita dapat menekan ke bawah bukan gerbang juga. Kita tahu bahwa ukuran rumus paritas adalah n ^ 2 (lihat Troy J. Lee, " Ukuran rumus PARITY ", 2007) dan karena pada setiap tingkat sirkuit kami, kami hanya dapat memiliki gerbang O (n), ini menunjukkan bahwa paritas tidak dalam . $AC^0_{bf}$ $AC^0_{bf}$

domotorp
sumber

jadi dengan "Formula" yang Anda maksud adalah rumus ukuran linier, bukan? dan berdasarkan ukuran yang Anda maksud ukuran formula ...

Alessandro Cosentino

O (2^{d} n)

$O(2^dn)$

d

$d$

d

$d$

Ini persis apa yang saya maksudkan, maaf jika eksposisi saya buruk.

domotorp

$S$ $S^d$ $S$ $S$ $AC^0$ $S^{1/d}$ $AC^0$ $AC^0$ $AC^0$ $d$

$X$ $1$ $n$

Stasys
sumber

S^{d}

$S^d$

k^{d} S

$k^dS$

k

$k$

S

$S$

A C_{b f}^{0}

$AC^0_{bf}$

A C^{0}

$AC^0$

k n

$kn$

k^{2} n

$k^2n$

O (n)

$O(n)$

A C^{0}

$AC^0$

A C_{b f}^{0}

$AC^0_{bf}$

Dapatkah seseorang memberi tahu saya mengapa model "tidak lebih dari k salinan variabel input" ini menarik? Bahkan ketika kedalamannya konstan. Dalam konteks apa model seperti itu muncul? Saya hanya ingin tahu.

Stasys

Q A C^{0}

$QAC^0$

A C^{0}

$AC^0$

n \log n

$n\log n$