Geradlinige Komplexität von Monomen

11

Sei ein Feld. Wie üblich definieren wir für f k [ x 1 , x 2 , , x n ] L ( f ) als die geradlinige Komplexität von f über k . Sei F die Menge der Monome von f , nämlich die Monome, die in f mit einem Koeffizienten ungleich Null erscheinen.kfk[x1,x2,,xn]L(f)fkFff

Stimmt es, dass ?mF:L(m)L(f)

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

Gorav Jindal
quelle

Antworten:

13

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=1nxi)2n
(2n+n1n1)2n2L(f)=O(n)2O(nlogn)O(n)fmL(m)=Ω~(L2(f))
domotorp
quelle
2
Als kleines konstruktives Beispiel, das auf der Antwort von domotorp basiert, kann man mit während . f=(x+y)8L(f)=4L(x7y)=L(x7)+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
1
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 2L2LxD2logDD n2nlogD+n1xiDiDiDf2L(f)2nL(f)+n1.
Bruno
1
@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 . nL(f)fL(f)+1nL(f)+1L(m)=O(L2(f))
Domotorp
8

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 , .f2L(f)mMdeg(m)2L(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 ).xdxd2log(d)m=x1d1xndnxidiL(m)2nlog(d)+(n1)dmdi

Zusammen erhält man für : mM

L(m)2nlog(deg(m))+(n1)2nL(f)+(n1).

Da , kann man nL(f)+1

mM,L(m)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