Finden Sie ein Polynom in zwei oder drei Abfragen

Blackbox von bedeutet, dass ich das Polynom an jedem Punkt auswerten kann . $f(x)$ $f(x)$

Eingabe : Eine Blackbox des monischen Polynoms des Grades . $f(x) \in\mathbb{Z}^+[x]$ $d$
Ausgabe: Die Koeffizienten des Polynoms . $d$ $f(x)$

Mein Algorithmus: lass

f (x) = x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{1} x + a_{0}

$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$

Werten Sie Polynom an vielen Punkten mit der Blackbox aus und erhalten Sie ein lineares Gleichungssystem. Jetzt kann ich das lineare Gleichungssystem lösen, um die gewünschten Koeffizienten zu erhalten. $\mathcal{f(x)}$ $d$

In diesem Fall benötige ich jedoch viele Anfragen an die Blackbox. Ich möchte die Anzahl der Anfragen minimieren . Gibt es eine Möglichkeit, die Anzahl der Abfragen auf zwei oder drei zu reduzieren? $\mathcal{O(d)}$

algorithms polynomials Komplexität
quelle

Sie ändern ständig die Frage. Vielleicht sollten Sie sich zuerst für eine Frage entscheiden und diese erst dann stellen. Ansonsten kann es für den Antwortenden etwas frustrierend sein.

Yuval Filmus

Was bedeutet ?

Z^{+}

$\mathbb{Z}^+$

md5

Reihe von positiven ganzen Zahlen

Komplexität

Übrigens können für Ihren Algorithmus die Koeffizienten in anstelle von mit der geschlossenen Lagrange-Formel berechnet werden.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

md5

Genau die gleiche Frage, anders formuliert: math.stackexchange.com/questions/446130/…

Nayuki

Antworten:

Sie können das Polynom mit zwei Abfragen ermitteln. Fragen Sie zuerst das Polynom bei , um eine Obergrenze für den Wert der Koeffizienten zu erhalten. Fragen Sie nun das Polynom bei Ihrer Wahl ab und lesen Sie die Koeffizienten aus der Basis- Erweiterung ab. $x=1$ $M$ $x > M$ $x$

Interessanterweise können Sie keine besseren erzielen als Abfragen , wenn Sie zulassen, dass die Koeffizienten negativ sind . In der Tat kann ich Ihre Anfragen mit Null beantworten , und dies legt den Wert des Polynoms nicht fest, da alle Polynome der Form stimmen mit meinen Antworten überein. $d$ $d-1$ $x_1,\ldots,x_{d-1}$ $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Yuval Filmus
quelle

Für Negative denke ich, dass 2's komplementärer Trick funktionieren könnte.

Komplexität

Nicht ohne eine Obergrenze für die Größe der Koeffizienten. Das zeigt mein Beweis.

Yuval Filmus

Entschuldigung, ich habe diesen Teil nicht bekommen "Ich kann Ihre

Fragen immer beantworten

von Null"

d - 1

$d-1$

x_{1}, \dots, x_{d - 1}

$x_1,\ldots,x_{d-1}$

Komplexität

Dies ist ein gegnerisches Argument. Ihr Algorithmus fragt die Blackbox nach dem Wert von

Stellen und antwortet immer mit Null. Ich zeige, dass dies nicht ausreicht, um den Wert von

abzuleiten .

f

$f$

d - 1

$d-1$

f

$f$

Yuval Filmus