Monotoniczne obwody arytmetyczne

Stan naszej wiedzy o ogólnych obwodach arytmetycznych wydaje się być podobny do stanu naszej wiedzy o obwodach boolowskich, tzn. Nie mamy dobrych dolnych granic. Z drugiej strony mamy wykładnicze granice wielkości dla monotonicznych obwodów boolowskich .

Co wiemy o monotonii obwodach arytmetycznych? Czy mamy dla nich podobne dobre dolne granice? Jeśli nie, to jaka jest zasadnicza różnica, która nie pozwala nam uzyskać podobnych dolnych granic dla monotonicznych obwodów arytmetycznych?

Pytanie jest inspirowane komentarzami do tego pytania .

Dolne granice monotonicznych obwodów arytmetycznych są łatwiejsze, ponieważ zabraniają anulowania. Z drugiej strony możemy udowodnić wykładnicze dolne granice dla obwodów obliczających funkcje boolowskie, nawet jeśli dowolne monotoniczne funkcje o wartościach rzeczywistych są dozwolone jako bramki (patrz np. Rozdz. 9.6 w$g:R\times R\to R$ książce ).

Chociaż monotone arytmetyczne obwody są słabsze niż monotonicznych logicznych układów (w tym ostatnim mamy odwołania ∧ = i ∨ ( ∧ b ) = ), obwody te są interesujące ze względu na ich stosunku do programowania dynamicznego (DP) algorytmów . Większość takich algorytmów można symulować za pomocą obwodów w półprzewodnikach ( + , min ) lub ( + , max )$a\land a=a$$a\lor (a\land b)=a$$(+,\min)$$(+,\max)$. Bramki odpowiadają następnie podproblemom używanym przez algorytm. Jerrum i Snir (w pracy V Vinay) faktycznie dowodzą, że każdy algorytm DP dla idealnego dopasowania minimalnej wagi (jak również dla problemu TSP) musi generować wykładniczo wiele podproblemów. Ale problem Perfect Mathching nie polega na „wadzie DP” (nie spełnia zasady optymalności Bellmana ). Programowanie liniowe (nie DP) jest znacznie bardziej odpowiednie dla tego problemu.

A co z problemami optymalizacji, które można rozwiązać za pomocą stosunkowo małych algorytmów DP - czy możemy udowodnić również dolne granice? Bardzo interesujący pod tym względem jest stary wynik Kerra (Twierdzenie 6.1 w jego doktoracie ). Oznacza to, że klasyczny algorytm DP Floyda-Warshalla dla problemu najkrótszych ścieżek wszystkich par (APSP) jest optymalny : konieczne są podproblemy . Jeszcze bardziej interesujące jest to, że argument Kerr jest bardzo prosty (znacznie prostszy niż Jerrum i Snir): po prostu używa aksjomatu dystrybucji a + min ( b , c ) = min ( $\Omega(n^3)$Aho, Hopcroft i Ullman pokazuje, że problem ten jest równoważny problemowi APSP. i możliwość „zabicia” min-bramek poprzez ustawienie jednego z argumentów na 0. W ten sposób dowodzi, że n 3 -bramek jest konieczne do pomnożenia dwóchmacierzy n × n przez semestr ( + , min ) . W rozdz. 5.9książki$a+\min(b,c)=\min(a,b)+\min(a,c)$$0$$n^3$$n\times n$$(+,\min)$

Następne pytanie może brzmieć: co z problemem najkrótszych ścieżek z jednego źródła (SSSP)? Algorytm Bellmana-Forda DP dla tego (pozornie „prostszego”) problemu wykorzystuje również bramki . Czy to jest optymalne? Jak dotąd nie jest znane rozdzielenie tych dwóch wersji problemu najkrótszej ścieżki; zobacz ciekawą gazetę Virginii i Ryana Williamsa. Tak więc świetnym wynikiem byłaby dolna granica Ω ( n 3 ) w obwodach ( + , min ) dla SSSP. Następne pytanie może brzmieć: a co z dolnymi granicami dla plecaka? W tym projekcie$O(n^3)$$\Omega(n^3)$$(+,\min)$ dolnych granic dla plecaka jest udowodniona w słabszym modelu obwodów których użycie $(+,\max)$$+$ bramek jest ograniczone; w załączniku dowód Kerr został odtworzony.

Tak. Znamy dobre dolne granice i znamy je już od dłuższego czasu.

Jerrum i Snir udowodnili wykładniczą dolną granicę monotonicznych obwodów arytmetycznych dla stałych do 1980 roku. Valiant wykazał, że nawet jedna bramka minus jest wykładniczo silniejsza .

Aby uzyskać więcej informacji na temat (monotonicznych) obwodów arytmetycznych, sprawdź ankietę Shpilki dotyczącą obwodów arytmetycznych.

Kolejny znany mi wynik to Arvind, Joglekar i Srinivasan - przedstawiają wyraźne wielomiany obliczalne na podstawie szerokości liniowej -$2k$ monotoniczne obwody arytmetyczne, ale dowolna szerokość$k$ monotoniczny obwód arytmetyczny przyjąłby rozmiar wykładniczy.

Czy to się liczy: dolne granice Chazelle dla podstawowych problemów z wyszukiwaniem zasięgu (w trybie offline). Wszystkie dolne granice są prawie optymalne (do logarytmów, gdy dolne granice są wielomianowe, i log logów, gdy dolna granica jest polilogarytmiczna).