Parzystość i

19

Parzystość i są jak nierozłączne bliźniaki. Tak przynajmniej wyglądało przez ostatnie 30 lat. W świetle wyników Ryana wznowione zostanie zainteresowanie małymi klasami. $AC^0$

Furst Saxe Sipser do Yao do Hastad są ograniczeniami parzystości i losowymi. Razborov / Smolensky jest przybliżonym wielomianem z parzystością (ok, mod bramki). Aspnes i wsp. Stosują słaby stopień parzystości. Ponadto Allender Hertrampf i Beigel Tarui używają Tody do małych klas. I Razborov / Beame z drzewami decyzyjnymi. Wszystkie one należą do koszyka parzystości.

1) Jakie są inne naturalne problemy (oprócz parzystości), które można wykazać bezpośrednio, że nie występują w ? $AC^0$

2) Czy ktoś wie o zupełnie innym podejściu do dolnej granicy na AC ^ 0, które zostało wypróbowane?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
źródło

13

Wynik Benjamina Rossmana dla dolnej granicy dla kliki k z STOC 2008. $AC^0$

Bibliografia:

Paul Beame, „ A Switching Lemma Primer ”, Raport techniczny 1994.
Benjamin Rossman, „ O stałej złożoności k-Clique ”, STOC 2008.

Kaveh
źródło

Czy Rossman nie jest podporządkowany podkładowi Beame'a, który również zawierał w nim klikę? Argumenty są oczywiście bardziej skomplikowane.

V Vinay,

@V Vinay: czy możesz podać link do artykułu Paula Beame'a?

Kaveh

4

Wynik Rossmana pokazuje, że

klika nie może być obliczona przez obwody o stałej głębokości o wielkości

. Zauważ, że stała w wykładniku nie zależy od głębokości obwodu, czyli tam, gdzie poprawia się na dolnej granicy wiązki

.

k

$k$

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

Srikanth,

@ Srikanth, myślałem, że V Vinay mówi, że Beame ma nowszy wynik, ale nie udało mi się znaleźć żadnego na jego stronie. Dzięki za wyjaśnienie.

Kaveh

1

Srikanth ma rację co do granic. Kaveh, nie nowy artykuł; Użyłem słowa „subsumed” w tym sensie, że wymieniłem Beame'a w moim pytaniu i dlatego byłem świadomy dolnej granicy kliki.

V Vinay,

12

Istnieje podejście „odgórne” Håstad, Jukna i Pudlák, tak jak to opisano w ich pracy „Od góry do dołu” dla obwodów na głębokości trzeciej . Niestety do tej pory nie byliśmy w stanie rozszerzyć podejścia na większe głębokości.

Kristoffer Arnsfelt Hansen
źródło

Tak. Myślałem, że masz wpływ na to podejście?

V Vinay

10

$AC^{0}$ przy użyciu tych samych technik. Szczegółowe informacje można znaleźć w pracy Håstad .

2) Kriegel i Waack zaproponowali podejście topologiczne, znów działające tylko dla obwodów o głębokości trzeciej .

Alessandro Cosentino
źródło

2

Większość tak naprawdę jest tym samym. Powinienem jednak o tym wspomnieć. Ponadto w połowie lat 80. pojawił się artykuł Boppany na temat większości.

V Vinay,

8

Pozostałe dwie „klasyczne” metody to metoda wąskiego gardła Hakena i metoda fuzji Karchmera (tak nazwana przez Avi Wigderson), obie o wiele łatwiejsze do zastosowania w ustawieniu monotonicznym.

Yuval Filmus
źródło

Parzystość i

Odpowiedzi: