Czy obwody arytmetyczne są słabsze niż logiczne?

Niech oznacza minimalny rozmiar (niemonotonowego) arytmetycznego obwodu obliczającego dany wielomianowy wielomian i oznaczają minimalny rozmiar ( obwodu logicznego obliczającego wersję logiczną z zdefiniowane przez: $A(f)$$(+,\times,-)$

$$f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,$$ $B(f)$$(\lor,\land,\neg)$ $f_b$$f$ $$f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,.$$

Czy znane są wielomiany dla których jest mniejsze niż ? $f$$B(f)$$A(f)$

Jeśli weźmiemy pod uwagę monotoniczne wersje obwodów - bez bramek Minus i bramek Not - to może być nawet wykładniczo mniejsze niż : weźmy na przykład najkrótszą wielomianową ścieżkę st na ; następnie i . Ale co dzieje się w „świecie niemonotonicznym”? Oczywiście, duże luki nie mogą być znane tylko dlatego, że nie mamy dużych dolnych granic na . Ale może znane są przynajmniej niektóre luki? $(-)$$(\neg)$$B(f)$$A(f)$$f$$K_n$$B(f)=O(n^3)$$A(f)=2^{\Omega(n)}$$A(f)$

---

UWAGA (15.03.2016) W moim pytaniu nie określiłem, jak duże współczynniki są dozwolone. Igor Siergiejew zapamiętał mnie, że na przykład następujący wielomian ma (Strassen i ludzie z jego grupy). Ale dla tego wielomianu, ponieważ . Można uzyskać fron do wielowymiarowego wielomianu z zmienne sterowanym przez Kronecker zastąpienia. Skojarzyć z każdym wykładnik a Jednomian , gdzie$c_e$$f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$$A(f)=\Omega(m^{1/2})$$B(f)=0$$f_b(z)=z$$f$$f'(x_1,\ldots,x_n)$$n=\log m$$j$$X_j=\prod_{i:a_i=1}x_i$$(a_1,\ldots,a_n)$są współczynnikami 0-1 binarnej reprezentacji . Zatem pożądanym wielomianem jest , i mamy to Ale wersja boolowska jest po prostu OR zmiennej, więc i mamy nawet wykładniczą lukę. Zatem jeśli wielkość współczynników może być potrójnie wykładnicza w liczbie zmiennych, to można wykazać, że przerwa jest nawet wykładnicza. (Właściwie to nie sama wielkość - bardziej algebraiczna zależność współczynników.) Właśnie dlatego prawdziwy problem z dotyczy małych$j$$f'=\sum_{j=1}^m c_j X_j$ $$A(f')+n\geq A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.$$ $f'$$B(f')\leq n-1$$n$$A(f)/B(f)$ $A(f)$współczynniki (idealnie tylko 0-1). Ale w tym przypadku, jak przypomniał Joshua, dolna granica Strassena i Baura (o współczynnikach 0-1) pozostaje najlepszym, co mamy dzisiaj.$A(f)=\Omega(n\log n)$

Wygląda na to, że permanent kwalifikuje się, przynajmniej warunkowo (tzn. Zakładając, że ). Zauważ, że boolowska wersja permanentu ma po prostu zdecydować, czy dany wykres dwudzielny ma idealne dopasowanie, które ma obwody wielowymiarowe.$\mathsf{VP}^0 \neq \mathsf{VNP}^0$

[Podsumowując poniższe komentarze:] Pomimo tego, że ten przykład jest warunkowy, nie można obecnie bezwarunkowo oczekiwać niczego poza luką logarytmiczną, ponieważ jest nadal najlepiej znaną dolną granicą ogólnych obwodów algebraicznych. Jak zauważył Stasys, tę logarytmiczną lukę osiąga funkcja (wymaga obwodów algebraicznych o rozmiarze przez Baura-Strassena), których logika jest logiczna wersja to tylko .$\Omega(n \log n)$$\sum_{i=1}^n x_i^n$$\Omega(n \log n)$$x_1 \vee x_2 \vee \dotsb \vee x_n$