Złożoność jednomianów w linii prostej

Niech będzie polem. Jak zwykle dla definiujemy jako złożoność linii względem linii prostej . Niech będzie zbiorem jednomianów , a mianowicie jednomianów, które występują w z niezerowym współczynniku. $k$ $f\in k[x_{1},x_{2},\ldots,x_{n}]$ $L(f)$ $f$ $k$ $F$ $f$ $f$

Czy to prawda, że ? $\forall m\in F:L(m)\le L(f)$

Znany jest nawet słabszy górny limit dla ? $L(m)$

cc.complexity-theory algebraic-complexity arithmetic-circuits

— Gorav Jindal
źródło

Odpowiedzi:

Jeśli to ma monomialów i . Argumentem liczącym są programy liniowe o długości . Ponieważ ma więcej monomialów, dla niektórych potrzebujemy dłuższego programu. W rzeczywistości argument ten podaje jednomianowy dla którego .

f = (Σ_{i = 1}^{n} x_{i})^{2^{n}}

$f=(\Sigma_{i=1}^n x_i)^{2^n}$

(\binom{2^{n} + n - 1}{n - 1}) \approx 2^{n^{2}}

${2^n+n-1\choose n-1} \approx 2^{n^2}$

L (f) = O (n)

$L(f)=O(n)$

2^{O (n \log n)}

$2^{O(n\log n)}$

O (n)

$O(n)$

f

$f$

m

$m$

L (m) = \tilde{Ω} (L^{2} (f))

$L(m)=\widetilde\Omega(L^2(f))$

— domotorp
źródło

Jako mały konstruktywny przykład oparty na odpowiedzi domotorp, można przyjąć przy podczas gdy .

f = (x + y)^{8}

$f=(x+y)^8$

L (f) = 4

$L(f)=4$

L (x^{7} y) = L (x^{7}) + 1 = 5

$L(x^7y)=L(x^7)+1=5$

— Bruno,

@domotorp, dzięki za miłą odpowiedź. Czy to też wydaje się być górną granicą? Czy mogą być lepsze dolne granice?

— Gorav Jindal,

Nie wiem, ale ponieważ ten przykład był tak prosty, zgaduję, że różnica może być większa, być może nawet wykładnicza.

— domotorp

Mam „dowód”, że istnieje liniowa górna granica ... Gdzie się mylę (skoro udowodniłeś kwadratową dolną granicę)? To, co następuje: Z SLP o rozmiarze , obliczyć wielomian całkowitego stopnia . Teraz ma SLP wielkości co najwyżej z potęgowaniem binarnym. Stopnio -variate Jednomian jest następnie SLP o wielkości co najwyżej (bardzo szorstki związany) obliczyć wszystkie , , a następnie ich produktów. Zatem jeśli weźmiemy pod uwagę wielomian , jego całkowity stopień wynosi co najwyżej , a każdy monomial ma SLP o wielkości co najwyżej

L

$L$

\leq 2^{L}

$\le 2^L$

x^{D}

$x^D$

2 \log D

$2\log D$

D

$D$

n

$n$

2 n \log D + n - 1

$2n\log D+n-1$

x_{i}^{D_{i}}

$x_i^{D_i}$

D_{i} \leq D

$D_i\le D$

f

$f$

2^{L (f)}

$2^{L(f)}$

2 n L (f) + n - 1

$2nL(f)+n-1$ .

— Bruno,

@Bruno: Niezły dowód i nie ma w tym nic złego, ale nie jest liniowy, ponieważ mnożymy i . Ale ponieważ wiemy, że może zależeć co najwyżej od zmiennych , możemy założyć , co implikuje wymagane ograniczenie kwadratowe. Zatem .

n

$n$

L (f)

$L(f)$

f

$f$

L (f) + 1

$L(f)+1$

n \leq L (f) + 1

$n\le L(f)+1$

L (m) = O (L^{2} (f))

$L(m)=O(L^2(f))$

— domotorp

Uwaga: Jest to rozwinięcie poprzedniego komentarza, ponieważ PO wyraźnie poprosił o słabsze górne granice.

Całkowity stopień wielomianu jest ograniczony przez ponieważ każda operacja może co najwyżej podwoić stopień wielomianu. Zatem dla każdego , . $f$ $2^{L(f)}$ $m\in M$ $\deg(m)\le 2^{L(f)}$

Teraz, dla pewnej zmiennej i stopnia , SLP konwertuje przez potęgowanie binarne, jeśli rozmiar nie przekracza . Dla monomialnego , można osobno obliczyć każdy a następnie wziąć ich iloczyn. Zatem gdzie jest całkowitym stopniem (który jest oczywiście górną granicą każdego ). $x$ $d$ $x^d$ $2\log(d)$ $m=x_1^{d_1}\dotsb x_n^{d_n}$ $x_i^{d_i}$ $L(m)\le 2n\log(d) + (n-1)$ $d$ $m$ $d_i$

Razem uzyskuje się dla : $m\in M$

L (m) \leq 2 n \log (\deg (m)) + (n - 1) \leq 2 n L (f) + (n - 1) .

$L(m)\le 2n\log(\deg(m))+(n-1)\le 2nL(f)+(n-1).$

Ponieważ , można dojść do $n\le L(f)+1$

\forall m \in M, L (m) \leq 2 L (f)^{2} + 3 L (f) .

$\forall m\in M, L(m) \le 2L(f)^2+3L(f).$

Uwagi Związane, jak stwierdzono, jest bardzo szorstkie. W szczególności górna granica podana na to drugi akapit, który nie jest ciasny. Jednak odpowiedź domotorp pokazuje, że nie można liczyć na znacznie lepszą granicę, a ściślej mówiąc, że nie można usunąć kwadratowej zależności od . Aby dokręcić konstrukcję, można zastosować najbardziej znane konstrukcje na łańcuchach dodatków . Zauważ, że dokładne granice wciąż nie są znane dla tego problemu. $L(m)$ $L(f)$

— Bruno
źródło