Obwód dolnych granic nad dowolnymi zestawami bramek

W latach 80. Razborov słynie, że istnieją wyraźne monotoniczne funkcje boolowskie (takie jak funkcja CLIQUE), które wymagają wykładniczo wielu bramek AND i OR do obliczenia. Jednak podstawa {AND, OR} ponad domeną logiczną {0,1} jest tylko jednym przykładem interesującego zestawu bramek, który nie jest uniwersalny. To prowadzi do mojego pytania:

Czy istnieje inny zestaw bramek, co ciekawe różni się od bram monotonnych, dla których znane są wykładnicze dolne granice wielkości obwodu (bez głębokości lub innych ograniczeń w obwodzie)? Jeśli nie, to czy istnieje jakikolwiek inny zestaw bram, który jest prawdopodobnym kandydatem na takie dolne granice - granice, które niekoniecznie wymagałyby przebicia się przez barierę Naturalnych Dowodów, ponieważ wynik obwodów monotonicznych Razborowa nie?

Jeśli taki zestaw bram istnieje, to na pewno będzie on ponad k-ary alfabet dla k≥3. Powodem jest to, że nad binarnym alfabetem

(1) monotonne bramy ({AND, OR}),

(2) bramy liniowe ({NOT, XOR}) i

(3) bramy uniwersalne ({AND, OR, NOT})

w zasadzie wyczerpują interesujące możliwości, jak wynika z twierdzenia o klasyfikacji Posta. (Zauważ, że zakładam, że stałe --- 0 i 1 w przypadku binarnym --- są zawsze dostępne za darmo.) Z bramkami liniowymi każda funkcja boolowska f: {0,1} ⁿ → {0,1} to obliczalny w ogóle jest obliczalny przez obwód o wielkości liniowej; z uniwersalnym zestawem, oczywiście jesteśmy przeciwko Naturalnym Dowodom i innym przerażającym barierom.

Z drugiej strony, jeśli weźmiemy pod uwagę zestawy bramek nad alfabetem 3- lub 4-symbolowym (na przykład), to otwiera się szerszy zestaw możliwości --- i przynajmniej według mojej wiedzy, możliwości te nigdy nie zostały w pełni zmapowane z punktu widzenia teorii złożoności (proszę mnie poprawić, jeśli się mylę). Wiem, że możliwe zestawy bram są szeroko badane pod nazwą „klony” w algebrze uniwersalnej; Chciałbym być bardziej zaznajomiony z tą literaturą, aby wiedzieć, co jeśli wyniki z tego obszaru oznaczają złożoność obwodów.

W każdym razie nie wydaje się wykluczone, że istnieją inne dramatyczne dolne granice obwodu, gotowe do udowodnienia, jeśli po prostu rozszerzymy klasę bramek o skończone alfabety, które jesteśmy gotowi rozważyć. Jeśli się mylę, powiedz mi dlaczego!

(Przeniesiono z komentarzy, jak sugerował Suresh. Uwaga: niektóre błędy w komentarzu zostały naprawione tutaj).

Dzięki Scott za świetne pytanie.

Scott zdaje się sugerować, że przyczyną trudności w dolnych granicach może być ograniczony język operacji w przypadku boolowskim. Argument Shannona, który pokazuje, że większość obwodów musi być duża, opiera się na luce między policzalną mocą ekspresyjną i niezliczoną liczbą obwodów. Ta luka wydaje się znikać, gdy alfabet ma co najmniej 3 symbole.

W przypadku rozmiaru alfabetu 2 (przypadek boolowski) sieć klonów jest w nieskończoność nieskończona i nazywana jest siecią Posta .

Krata Posta wyjaśnia również, dlaczego istnieje tylko kilka interesujących podstaw operacji dla przypadku boolowskiego.

Dla wielkości alfabetu 3 lub większej sieć klonów jest niepoliczalna. Ponadto, sieć nie spełnia żadnej nietrywialnej tożsamości sieci, więc wydaje się niemożliwe przedstawienie pełnego opisu sieci. W przypadku rozmiaru alfabetu 4 lub większego sieć klonów faktycznie zawiera każdą skończoną sieć jako sublattice. Istnieje więc nieskończenie wiele interesujących podstaw operacji, które należy wziąć pod uwagę, gdy alfabet ma 3 lub więcej symboli.

• Bulatov, Andrei A., Warunki spełnione przez sieci klonowania , Algebra Universalis 46 237–241, 2001. doi: 10.1007 / PL00000340

Scott zapytał dalej: czy sieć klonów pozostaje niepoliczalna, jeśli założymy, że stałe są dostępne za darmo?

Odpowiedź brzmi: tak, na przykład

• Gradimir Vojvodić, Jovanka Pantović i Ratko Tošić, Liczba klonów zawierających funkcję jednoargumentową , NSJOM 27 83–87, 1997. ( PDF )
• J. Pantović, R. Tošić i G. Vojvodić, Liczebność funkcjonalnie pełnych algeb na zestawie trzech elementów , Algebra Universalis 38 136–140, 1997. doi: 10.1007 / s000120050042

chociaż najwyraźniej zostało to opublikowane wcześniej:

• Ágoston, I., Demetrovics, J., i Hannák, L. W sprawie liczby klonów zawierających wszystkie stałe , Coll. Matematyka Soc. János Bolyai 43 21–25, 1983.

Ładne konkretne stwierdzenie pochodzi z:

• A. Bulatov, A. Krokhin, K. Safin i E. Sukhanov, O strukturze sieci klonowania , W: „General Algebra and Discrete Mathematics”, red. K. Denecke i O. Lueders, 27–34. Heldermann Verlag, Berlin, 1995. ( PS )

$k \ge 3$$\mathcal{L}_k$$2^{\aleph_0}$

Podsumowując, nie jestem świadomy żadnej pracy związanej z użyciem nie-boolowskich klonów dla dolnych granic obwodu. Wydaje się, że warto to zbadać bardziej szczegółowo. Biorąc pod uwagę stosunkowo niewiele wiadomo o sieci klonów, mogą istnieć ciekawe podstawy operacji czekających na odkrycie.

Więcej powiązań między teorią klonowania a informatyką prawdopodobnie zainteresowałoby matematyków pracujących w algebrze uniwersalnej. Poprzedni przykład tego rodzaju interakcji miał miejsce, gdy Peter Jeavons wykazał, że algebry można powiązać z językami ograniczeń, w sposób, który pozwala na przełożenie wyników podatności na właściwości algebry. Andrei Bulatov wykorzystał to do udowodnienia dychotomii dla CSP o wielkości domeny 3. Idąc w drugą stronę, nastąpiło ożywienie zainteresowania oswojoną teorią zgodności w wyniku zastosowania informatyki. Zastanawiam się, co wynikałoby z powiązania między teorią klonowania a złożonością obwodów innych niż logiczne.

Zostało to przeniesione z komentarzy, jak sugerował Suresh.

$f:{0,1}^n \rightarrow {0,1}^n$$\Omega(\frac{n^2}{\log(n)})$

$\frac{n^2}{\log(n) * c}$$c$

$\Omega(n log n)$$\Omega(n^{3/2})$

Edycja 2. Główną przeszkodą jest to, że nie mamy żadnych metod dowodzenia nieliniowych dolnych granic nawet dla bram liniowych, o ile mi wiadomo (dla liniowych dolnych granic można zastosować eliminację bramki, co jest bardzo mało prawdopodobne, aby dać -liniczne granice). Choć wygląda na to, że niektóre metody z algebry liniowej naprawdę muszą być pomocne. Tak więc wymyślanie kandydatów jest fajne, ale i tak potrzebne są nowe metody.

1. $\{0,1\}$$a$$Z_3^n=\{0,1,2\}^n$$\min(x,y)$$xy\mod{2}$a 0 2 a 1 2 n / $f(a)=0$$a$$0$$2$jest w jest co najmniej liczbę 'S. Pokazuje, że dowolny obwód (powyżej tej wartości MIN / XOR) wymaga około bramek do obliczenia . Ale tak było! Nie jestem świadomy żadnych dalszych rezultatów w podobnej przysługi (przechodzenie do większych, ale wciąż skończonych domen), z wyjątkiem, oczywiście, rzeczy w obwodach arytmetycznych. Ale tylko dla obwodów - dla programu rozgałęziającego przechodzenie do większych domen sprawia, że ​​zadanie dolnej granicy jest nieco łatwiejsze. $a$$1$$2^n/\sqrt{n}$$f$

2. Na obwodach z bramkami XOR. Tutaj nawet przypadek głębokości jest szeroko otwarty. Najwyższe dolne granice dla jawnych przekształceń liniowych nad mają postać . Udowodnienie powiązania takiego jak dla stałej , nawet na głębokości i nawet jeśli dozwolone są tylko bramki XOR, jest wyzwaniem.R = x G- F, ( 2 ) n log 3 / 2 n n 1 + c c > 0 $2$$y=Ax$$GF(2)$$n\log^{3/2}n$$n^{1+c}$$c>0$$2$