Dlaczego bramy mod_m są interesujące?

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?

$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.

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]$

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.