Dlaczego dolne granice dla obwodów boolowskich nie implikują niższych granic obwodów arytmetycznych

Moje pytanie brzmi: dlaczego dolne granice dla głębokości 3 Obwody logiczne z bramkami „i” i „xor” dla wyznacznika nie oznaczają takich samych dolnych granic dla obwodów arytmetycznych w ?$\mathbb{Z}$

Co jest nie tak z następującym argumentem: Niech będzie wyznacznikiem obliczającym obwód arytmetyczny, a następnie biorąc wszystkie zmienne mod 2 otrzymamy wyznacznik obliczania obwodu logicznego. $C$

W przypadku obwodów arytmetycznych przez $\mathbb{Z}$ twój argument jest słuszny. Ten sam argument działa dla obwodów arytmetycznych nad $\mathbb{Q}$ które nie używają żadnych ułamków $a/b$ gdzie $b$ jest parzyste.

Jednak argument nie działa, jeśli mówisz o obwodach arytmetycznych nad innymi pierścieniami, takich jak: ogólne obwody arytmetyczne nad (tj. Bez powyższego ograniczenia), , pola liczb algebraicznych, lub pola skończone pomocą .$\mathbb{Q}$$\mathbb{R}$$\mathbb{C}$$\mathbb{F}_{q}$$q \neq 2$

(Jest to zasadniczo ten sam powód, dla którego w geometrii algebraicznej jest często uważany za tak zwaną „charakterystykę mieszaną”, a nie charakterystykę zero.)$\mathbb{Z}$

Jednak dolne granice logiczne głębokości 3 dla obwodów z {AND, OR, NOT} są mniej łatwo powiązane z dolnymi granicami dla obwodów arytmetycznych w . (Tak, {AND, XOR} to kompletna podstawa, ale zazwyczaj obwody o głębokości 3 na {AND, OR, NOT} uważasz, że bramy NIE są darmowe, podczas gdy implementując NIE z XOR, używasz bramki XOR, którą faktycznie liczysz Podobnie, chociaż , kiedy zaimplementujesz tę pojedynczą bramę OR za pomocą AND i XOR, otrzymasz mały gadżet o głębokości 3.)$\mathbb{Z}$$a \vee b = \neg (\neg a \wedge \neg b)$

Ogólne stwierdzenie brzmi: niech będzie wielomianem o współczynnikach w pierścieniu , i załóżmy, że jest homomorfizmem pierścienia. Stosując do każdego współczynnika , otrzymujesz wielomian ze współczynnikami w , który . Zatem dolna granica dla obliczania przez obwody arytmetyczne implikuje tę samą dolną granicę dla obliczania przez obwody arytmetyczne$f$$R$$\varphi\colon R \to S$$\varphi$$f$$S$$f_S$$f_S$$S$$f$$R$