Dlaczego bramy mod_m są interesujące?

39

Ryan Williams właśnie opublikował swoją dolną granicę na ACC , klasie problemów, które mają obwody o stałej głębokości z nieograniczonym wachlowaniem i bramkami AND, OR, NOT i MOD_m dla wszystkich możliwych m.

Co jest takiego specjalnego w bramach MOD_m?

Pozwalają symulować arytmetykę na dowolnym pierścieniu Z_m.
Przed wynikiem Ryana rzucanie bramek MOD_m w miks dało pierwszą klasę, dla której znane dolne granice nie działały.

Czy istnieje jakiś inny naturalny powód, aby studiować bramy MOD_m?

— Dana Moshkovitz
źródło

39

$ACC^0$ to naturalna klasa złożoności.

1) Barrington wykazał, że obliczenia na monoidach nierozpuszczalnych wychwytują a na monoidach rozwiązywalnych przechwytują . $NC^1$ $ACC^0$

2) Ostatnio Hansen i Koucky udowodnili piękny wynik, że programy rozgałęzień płaskich o wielkiej wielkości mają dokładnie . Bez warunku płaskości otrzymujemy oczywiście wynik Barringtona charakteryzujący . $ACC^0$ $NC^1$

Zatem różnica między i jest z jednej strony teoretyczna dla grupy, az drugiej topologiczna. $ACC^0$ $NC^1$

Dodano: Dana, prostym przykładem grupy do rozwiązania jest , symetryczna grupa nad elementami. Bez wnikania w szczegóły każda rozwiązalna grupa ma szereg, którego iloraz zdarza się cykliczny. Ta cykliczna struktura zostaje odzwierciedlona w postaci modów podczas budowania obwodu w celu rozwiązania problemów słownych w grupie. $S_4$

Jeśli chodzi o planarność, chciałoby się wierzyć, że planarność może nakładać ograniczenia / wąskie gardła w przepływie informacji. Nie zawsze jest to prawdą: na przykład odmiany płaskiego 3SAT są znane jako NP-zupełne. Jednak w mniejszych klasach te ograniczenia są bardziej „prawdopodobne”.

W podobny sposób Wigderson wykazał NL / poli = UL / poli przy użyciu lematu izolacyjnego. Nie wiemy, jak odandomizować lemat izolacji względem dowolnych DAG, aby uzyskać NL = UL, ale wiemy, jak to zrobić w przypadku płaskich DAG.

— V Vinay
źródło

1

Dzięki wielkie za informację! Chciałbym usłyszeć więcej o intuicji tych wyników. Jeśli chodzi o moje pytanie: twój argument jest w gruncie rzeczy, że głębokość [O (log n), bramki AND, OR, NOT] jest naturalna, a jest jej niewielką odmianą (w stosunku do monoidów rozwiązalnych zamiast nierozpuszczalnych lub do płaskich, a nie niepłaskich programów rozgałęziających). Czy mógłbyś trochę rozwinąć: podać przykłady interesujących monoidów do obliczeń i jak ważna jest ich rozpuszczalność? Czy istnieje a priori motywacja do zainteresowania się tym, czy program rozgałęziający jest planarny, czy nie?

N C^{1}

$NC^1$

A C C

$ACC$

— Dana Moshkovitz,

7

Uzupełnienie: 1) Obliczenia na aperiodycznych monoidach wychwytują (Barrington i Thérien). 2) Programy rozgałęziające w górę do przechwytywania (Barrington, Lu, Miltersen, Skyum).

A C^{0}

$AC^0$

A C^{0}

$AC^0$

— Kristoffer Arnsfelt Hansen

@Vinay: Czy jesteś pewien, że wynik NL / poly = UL / poly jest wynikiem Wigdersona?

— Dai Le

17

Być może nie jest to tak naprawdę odpowiedź na twoje pytanie. Ale aby podać tylko jeden przykład, dlaczego czasami bramy (dla kompozytowych ) są silniejsze niż bramy : $\bmod m$ $m$ $\bmod p$

Rozważ klasę obwodów o stałej głębokości, które składają się tylko z , wejść i stałych na liściach. Następnie można łatwo wykazać, że funkcja OR (na przykład) nie może być obliczona przez takie obwody, niezależnie od wielkości obwodu. (Jest tak, ponieważ każdy taki obwód oblicza wielomian niskiego stopnia na , a stopień OR wynosi ). $\bmod p$ $\mathbb{F}_p$ $n$

Jeśli jednak weźmiemy pod uwagę obwody składające się tylko z których ma co najmniej dwa różne czynniki pierwsze, istnieje obwód głębokości (o wielkości wykładniczej) dla funkcji OR. $\bmod m$ $m$ $2$

A przed wynikiem Ryana był chyba najmniejszą klasą, dla której nie mieliśmy przyzwoitych dolnych granic. $AC^0[\bmod 6]$

— Ramprasad
źródło

1

Dodatek do ostatniego zdania: Wiadomo już, że obliczenie z o stałej głębokości przy użyciu bramek AND, OR, NOT i dla liczb pierwszych wymagało wykładniczej liczby bramek. (Istnieje również rozszerzenie względnie głównych kompozytów.) Ponieważ 6 jest najmniejszym złożeniem dwóch różnych liczb pierwszych, jest „najłatwiejszą” funkcją obliczeniową, dla której nie była znana wykładnicza dolna granica.

M O D_{q}

$MOD_q$

M O D_{p}

$MOD_p$

p \neq q

$p \ne q$

M O D_{6}

$MOD_6$

— Daniel Apon,

14

Aby rozwinąć swoje dwa punkty:

Jeśli zajmujemy się rozumieniem obliczeń, liczenie modułowe jest jedną z granic naszego zrozumienia. Liczenie modułowe jest jednym z najprostszych i najbardziej naturalnych zjawisk w obliczeniach, ale wydaje się, że tak mało go rozumiemy. Nie możemy wykluczyć, że obwody o głębokości 3 wielomianu z bramkami tylko Mod6 mogą obliczyć każdą funkcję w NP. Przypuszcza się jednak, że takie obwody mogą obliczać tylko funkcje o dużym rozmiarze wsparcia, a zatem nie mogą obliczać bardzo prostej funkcji, takiej jak AND. W górnej części sytuacja jest podobna, nie mamy nietrywialnych wyników.

Te pytania są również bardzo interesujące z czysto matematycznego punktu widzenia, ponieważ są ściśle powiązane z bardzo naturalnymi pytaniami dotyczącymi wielomianów i macierzy w Z_m. Aby podać jeden przykład, nie mamy dobrych dolnych granic dla rangi macierzy kodi nxn nad Z_6. Matryca kodiagonalna ma zero na przekątnej i nonzeros na przekątnej.

— aada
źródło

Osoby zainteresowane „modułem podstawowym i kompozytowym” powinny sprawdzić stronę domową Vince'a Grolmusza: grolmusz.pitgroup.org

— Stasys