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