PARITY

jest klasa układów wielomian wielkości stałej głębokości z nie bram i bezgranicznej fan-in i i lub bram, gdzie wejścia i bramy mają również nieograniczony Fanout. $AC^0$

Rozważmy teraz nową klasę, nazwijmy ją która jest jak ale dla której wejścia i bramki mają co najwyżej . Ta klasa jest wyraźnie w . W rzeczywistości jest to ściśle zawarte w , jak zauważono tutaj . Dlatego PARITY oczywiście nie jest w . $AC^0_{bf}$ $AC^0$ $O(1)$ $AC^0$ $AC^0$ $AC^0_{bf}$

Czy istnieje dowód na który również nie przechodzi przez ? Innymi słowy, czy istnieje dowód, który nie wykorzystuje zaawansowanych technik, takich jak lemat zamiany lub metoda Razborova / Smoleńskiego? $\notin AC^0_{bf}$ $AC^0$

cc.complexity-theory circuit-complexity Adam Paetznick
źródło

Nazywa się to

w literaturze: qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0

{N C}^{0}

$\mathsf{NC}^0$

Hsien-Chih Chang 之之

Nie, nie jest, ponieważ fanin jest nieograniczony.

domotorp

Ach, źle odczytałem słowo fanout. Dzięki za wskazanie.

Hsien-Chih Chang 張顯之

Powiązany post autorstwa @Kaveh: cstheory.stackexchange.com/q/1824/1800 , przeniesiony z poniższych komentarzy w celu zwiększenia ekspozycji.

Hsien-Chih Chang 張顯之

Nawiasem mówiąc, czym jest „fanout ograniczony”?

xxx ---

Odpowiedzi:

Mogę coś przeoczyć, ale czy tym samym co Formuła? Ponieważ każdy bit wejściowy może mieć wpływ na co najwyżej ograniczoną liczbę bramek, możemy po prostu założyć, że każda bramka ma tylko jedno wyjście (po ewentualnym powieleniu kilku rzeczy) i możemy również przesuwać w dół, a nie bramek. Wiemy, że formuła wielkości parzystości wynosi n ^ 2 (patrz Troy J. Lee, „ Formuła wielkości PARITY ”, 2007) i ponieważ na każdym poziomie naszego obwodu możemy mieć tylko bramy O (n), pokazuje to, że parzystość nie jest w . $AC^0_{bf}$ $AC^0_{bf}$

domotorp
źródło

więc przez „Formułę” rozumiesz formułę rozmiaru liniowego, prawda? a przez rozmiar rozumiesz formułę rozmiar ...

Alessandro Cosentino

Myślę, że twoja odpowiedź jest poprawna, ale rozumowanie jest bardziej subtelne. Rozgałęzienie bramki można zmniejszyć, kopiując części obwodu, ale zwiększa to rozmiar formuły. (Rozmiar formuły jest równoważny liczbie drutów wejściowych.) Powiedz, że fanout bramki wynosi co najwyżej 2. Następnie, aby zmniejszyć fanout bram dolnej warstwy, muszę zduplikować każdą bramę i każde wejście, podwajając rozmiar formuły. Powtórzenie tego procesu dla każdej warstwy daje formułę rozmiaru

gdzie

jest głębokością obwodu. W naszym przypadku

jest stałą, więc rozmiar formuły jest nadal liniowy.

O (2^{d} n)

$O(2^dn)$

d

$d$

d

$d$

Adam Paetznick

Dokładnie o to mi chodziło, przepraszam, jeśli moja ekspozycja była kiepska.

domotorp

@Alessandro: Przykro mi, jeśli źle zrozumiałem twoje pytanie. Ale moje pierwsze wrażenie jest takie, że można przekształcić dowolny obwód głębokości d rozmiaru w formułę głębokości d (fanout 1) o rozmiarze około : po prostu idź warstwa po warstwie, zaczynając od dołu (obok danych wejściowych) nałożyć warstwę i pobrać wiele kopii tej samej bramy; na każdej z warstw ilość bramek może zwiększyć się najwyżej o czynnik . Oznacza to, że dowolna dolna granica dla wzorów implikuje dolną granicę dla obwodów $S$ $S^d$ $S$ $S$ $AC^0$ $S^{1/d}$ $AC^0$ . Tak, to trudno oczekiwać łatwiej dolna granica dowody na wzorach: w świecie , jest stałą. $AC^0$ $AC^0$ $d$

Przy okazji twój język (ciągi dokładnie z ) ma trywialny DNF ( wzór głębokości-2 ) z monomialami. $X$ $1$ $n$

Stasys
źródło

Wydaje mi się, że możemy to zrobić lepiej niż

od fan-out są ograniczone, możemy uzyskać

, gdzie

jest max fan-out. Ponadto, ponieważ każdy bit wejściowy jest wykorzystywany tylko ograniczoną liczbę razy, rozmiar obwodu (

) jest liniowy.

S^{d}

$S^d$

k^{d} S

$k^dS$

k

$k$

S

$S$

Kaveh

Innym sposobem, aby zobaczyć, że

jest ściśle zawarty w

jest zauważenie, że ponieważ każdy bit wejściowy ma rozkład wentylacji co najwyżej k, w pierwszej warstwie jest co najwyżej

bramek, a

A C_{b f}^{0}

$AC^0_{bf}$

A C^{0}

$AC^0$

k n

$kn$

k^{2} n

$k^2n$ bramek w druga warstwa i tak dalej. Ponieważ głębokość jest stała, oznacza to, że obwód ma w sumie bramy

. Zatem żadna funkcja

która wymaga obwodów o rozmiarach nieliniowych, nie występuje w

O (n)

$O(n)$

A C^{0}

$AC^0$

A C_{b f}^{0}

$AC^0_{bf}$

Robin Kothari

Czy ktoś może mi powiedzieć, dlaczego ten model „nie więcej niż k kopii zmiennej wejściowej” jest interesujący? Nawet gdy głębokość jest stała. W jakim kontekście powstaje taki model? Jestem po prostu ciekawy.

Stasys,

@Stasys, Zarówno Adam, jak i moje pytanie wynikają z pracy nad klasą kwantową

, która jest zdefiniowana bez bramki fanout.

Q A C^{0}

$QAC^0$

Alessandro Cosentino

@Adam: Dzięki rzeczywiście domotorp wspomniano niebędącą

argument (Khrapchenko). Jakzauważył cstheory.stackexchange.com/questions/1824/...Robin Kothari, istnieje jeszcze jeden taki argument, że Krichevskii pokazuje, że funkcja progu-2 potrzebuje formuł wielkości około

. Co więcej, wiadomo, żewszystkie z wyjątkiem 16 symetrycznychfunkcji boolowskich wymagają formuł o rozmiarze nieliniowym. Tak więc na twoje pytanie zdecydowanie odpowie „tak”.

A C^{0}

$AC^0$

n \log n

$n\log n$

Stasys