Geradlinige Komplexität von Monomen

Sei ein Feld. Wie üblich definieren wir für als die geradlinige Komplexität von über . Sei die Menge der Monome von , nämlich die Monome, die in mit einem Koeffizienten ungleich Null erscheinen. $k$ $f\in k[x_{1},x_{2},\ldots,x_{n}]$ $L(f)$ $f$ $k$ $F$ $f$ $f$

Stimmt es, dass ? $\forall m\in F:L(m)\le L(f)$

Auch eine schwächere Obergrenze für ist bekannt? $L(m)$

cc.complexity-theory algebraic-complexity arithmetic-circuits Gorav Jindal
quelle

Antworten:

Wenn dann hat es Monome und . Nach einem Zählargument gibt es geradlinige Programme der Länge . Da mehr Monome hat, brauchen wir für einige ein längeres Programm. Tatsächlich ergibt dieses Argument ein Monom für das .

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
quelle

Als kleines konstruktives Beispiel, das auf der Antwort von domotorp basiert, kann man mit während .

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, Danke für die nette Antwort. Scheint dies auch die Obergrenze zu sein? Oder kann es bessere Untergrenzen geben?

Gorav Jindal

Ich weiß es nicht, aber da dieses Beispiel so einfach war, würde ich vermuten, dass die Lücke größer sein kann, möglicherweise sogar exponentiell.

Domotorp

Ich habe einen "Beweis" dafür, dass es eine lineare Obergrenze gibt ... Wo irre ich mich (da Sie eine quadratische Untergrenze bewiesen haben)? Es ist wie folgt: Bei einem SLP der Größe , können Sie ein Polynom gesamten Grades berechnen . Jetzt hat einen SLP von höchstens mit binärer Exponentiation. Ein Monom mit Grad -Variate hat dann einen SLP mit einer Größe von höchstens (sehr grob gebunden): Berechnen Sie alle , und dann ihr Produkt. Wenn wir also ein Polynom , beträgt sein Gesamtgrad höchstens , und jedes Monom hat einen SLP mit einer Größe von höchstens 2

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: Netter Beweis und es ist nichts falsch daran, aber es ist nicht linear, wenn Sie und multiplizieren . Da wir jedoch wissen, dass von höchstens Variablen abhängen kann , können wir annehmen , was die erforderliche quadratische Grenze impliziert. Somit ist .

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

Hinweis: Dies ist eine Erweiterung eines früheren Kommentars, da das OP ausdrücklich nach schwächeren Obergrenzen gefragt hat.

Der Gesamtgrad des Polynoms ist durch da jede Operation den Grad des Polynoms höchstens verdoppeln kann. Somit wird für jedes , . $f$ $2^{L(f)}$ $m\in M$ $\deg(m)\le 2^{L(f)}$

Nun gibt es für einige Variablen und Grad einen SLP, der durch binäre Exponentiation konputiert, wenn die Größe höchstens beträgt . Für ein Monom kann man jedes separat berechnen und dann sein Produkt nehmen. Somit ist wobei der Gesamtgrad von (was natürlich eine Obergrenze für jedes ). $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$

Zusammen erhält man für : $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).$

Da , kann man $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).$

Bemerkungen. Die Bindung ist wie angegeben sehr grob. Insbesondere ist die Obergrenze für die im zweiten Absatz angegeben ist, nicht eng. Die Antwort von domotorp zeigt jedoch, dass man nicht auf eine viel bessere Bindung hoffen kann und genauer gesagt, dass die quadratische Abhängigkeit von nicht beseitigt werden kann. Um die Konstruktion zu straffen, könnte man die bekanntesten Konstruktionen an Additionsketten verwenden . Beachten Sie, dass die genauen Grenzen für dieses Problem noch nicht bekannt sind. $L(m)$ $L(f)$

Bruno
quelle