Złożoność obwodu funkcji większości

13

Niech będzie funkcją większościową, tj. wtedy i tylko wtedy, gdy . Zastanawiałem się, czy istnieje prosty dowód na następujący fakt (przez „prosty” mam na myśli to, że nie polegałem na metodzie probabilistycznej, jak Valiant 84, ani na sieciach sortujących; najlepiej zapewniając wyraźną, prostą konstrukcję obwodu): $f: \{0,1\}^n \to \{0,1\}$ $f(x) = 1$ $\sum_{i = 1}^n x_i > n/2$

można obliczyć na podstawie rodziny obwodów ogłębokości , wielkości poli (n), gdzie bramki składają się z bramek NOT, bramek OR z 2 wejściami i bramek AND z 2 wejściami. $f$ $O(\log(n))$

— matthon
źródło

6

Może to być interesujące: Igor Siergiejew, Górne granice wielkości formuły funkcji większości ; także tutaj ogłasza nieco lepsze górne granice. Jeśli jednak zapytasz o tylko obwody (nie formuły ), to jak przypomniał mi Igor, każda symetryczna funkcja boolowska (nie tylko większość) ma obwód o głębokości

i rozmiarze

: wystarczy obliczyć sumę

s, i zrealizuj funkcję logiczną zmiennych

. Dla większości ta ostatnia funkcja jest porównaniem z

O (\log n)

$O(\log n)$

O (n)

$O(n)$

1

$1$

\log_{2} n

$\log_2n$

.

n / 2

$n/2$

— Stasys

@Stasys, a obliczenie liczby z nich polega zasadniczo na sortowaniu bitów.

— Kaveh

9

Odpowiedź Kaveh zapewnia odpowiedź na pytanie jak zrobić masz Stwierdził on (i to jest zwykle dowodem na wykazanie, że jest zawarta w ). Ale myślałem, że mógłbyś chcieć zadać nieco inne pytanie. Mianowicie dla jednoznacznej formuły monotonicznej wielkości wielomianowej dla większości. $\mathsf{TC}^0$ $\mathsf{NC}^1$

Ponieważ większość jest monotoniczna, wiemy, że można ją obliczyć na podstawie formuły monotonicznej. Istnieją dwie znane konstrukcje monotonicznych wzorów wielomianowych, a mianowicie dwie, o których wspominasz, probabilistyczna konstrukcja Valiant i konstrukcja za pośrednictwem sieci sortujących. O ile mi wiadomo, nie mamy prostszej konstrukcji deterministycznej niż ta zapewniana przez sieci sortujące.

Powiązane z tym jest również następujące. Okazuje się, że większość może być obliczany za pomocą wzorów, który składa się tylko bramy (i bez żadnych stałych!). Konstrukcję probabilistyczną Valianta można dostosować, aby uzyskać takie wzory o głębokości . Jednak tutaj nie znamy deterministycznej konstrukcji. W szczególności sieci sortujących nie nadają się do tego (przyczyn technicznych: mają zapewnić wszystkie funkcje progu i działają tylko większość może być obliczona na wszystkim bram). Poczyniono jednak ostatnie postępy w tej kwestii podanej w artykule $\mathsf{MAJ}_3$ $O(\log(n))$ $\mathsf{MAJ}_3$ Efektywne wielopartyjne protokoły za pomocą wzorów progów głębokości logów Cohen i in. Tutaj takie formuły są oparte na standardowych założeniach teoretycznych lub kryptograficznych.

— Kristoffer Arnsfelt Hansen
źródło

9

Obliczanie ograniczonej wartości progowej ( ) zasadniczo sortuje bity wejściowe. $\sum_i x_i \geq k$

Jeśli możesz posortować bity, łatwo jest porównać wynik z i obliczyć próg ograniczony. $k$

Z drugiej strony załóżmy, że mamy obwody do obliczania ograniczonego progu. Możemy przeprowadzić równoległe wyszukiwanie, aby znaleźć liczbę jedynek na wejściu i wyświetlić posortowaną listę.

$\mathsf{NC^1}$ $O(\lg n)$ $\mathsf{NC^1}$ $O(\lg n)$

Zauważ, że łatwo jest wprowadzić próg ograniczony przy użyciu większości, dodając nowe wejścia 1 i 0 do bramki większości.

$\mathsf{AC^0}$ $\mathsf{AC^1}$ $\mathsf{NC^2}$

$O(\lg n)$

$a,b,c$ $x,y$ $a+b+c = x+y$

$O(1)$

Patrz sekcja 4 i ćwiczenie 4 w

David Mix Barrington i Alexis Maciel, „ Advanced Course on Computational Complexity ”, wykład 6, IAS / PCMI, 2000.

— Kaveh
źródło

O (\lg n)

$O(\lg n)$

O (\lg n)

$O(\lg n)$

7

$n$

Alternatywnym dowodem są Brodal i Husfeldt: Dowód złożoności komunikacji, że funkcje symetryczne mają głębokość logarytmiczną . Ponownie, dowód jest elementarny i zapewnia wyraźną konstrukcję.

— Alexander S. Kulikov
źródło