Finden Sie ein Polynom in zwei oder drei Abfragen

17

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

  • Eingabe : Eine Blackbox des monischen Polynoms des Grades .df(x)Z+[x]d

  • Ausgabe: Die Koeffizienten des Polynoms .f ( x )df(x)

Mein Algorithmus: lass

f(x)=xd+ad1xd1++a1x+a0

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. df(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?O(d)

Komplexität
quelle
2
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
2
Was bedeutet ? Z+
md5
1
Reihe von positiven ganzen Zahlen
Komplexität
1
Übrigens können für Ihren Algorithmus die Koeffizienten in anstelle von mit der geschlossenen Lagrange-Formel berechnet werden. O ( n 3 )O(n2)O(n3)
md5
2
Genau die gleiche Frage, anders formuliert: math.stackexchange.com/questions/446130/…
Nayuki

Antworten:

29

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=1Mx>Mx

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 - 1 x 1 , , x d - 1 ( x - x 1 ) ( x - x d - 1 ) ( x - x d )dd1x1,,xd1(xx1)(xxd1)(xxd)

Yuval Filmus
quelle
Für Negative denke ich, dass 2's komplementärer Trick funktionieren könnte.
Komplexität
4
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 x 1 , ... , x d - 1 von Null"d1x1,,xd1
Komplexität
6
Dies ist ein gegnerisches Argument. Ihr Algorithmus fragt die Blackbox nach dem Wert von an d - 1 Stellen und antwortet immer mit Null. Ich zeige, dass dies nicht ausreicht, um den Wert von f abzuleiten . fd1f
Yuval Filmus