Um eine Gleichung zu lösen, rät ein Computer oft, prüft und rät dann erneut. Jede Runde landet näher an der Antwort. Doch wie viel näher kann eine einzelne Runde kommen?
Das Newton-Verfahren stellt pro Runde zwei Fragen: den Wert der Funktion und ihre Steigung. Nahe an der Antwort verdoppelt sich dann die Zahl der korrekten Stellen in jeder Runde.
1974 vermuteten Kung und Traub eine Geschwindigkeitsgrenze. Mit n Fragen pro Runde kann die Ordnung niemals 2 hoch n−1 übersteigen. Sie hatten Verfahren gebaut, die diese Grenze erreichen. Niemand konnte beweisen, dass sie unschlagbar ist.
Matthew Colbrook aus Cambridge hat es nun bewiesen. Der Trick: Funktionen konstruieren, die dieselben Antworten geben, ihre Nullstelle aber anderswo verstecken. Ein Beweisassistent, Lean, hat das Ergebnis geprüft.
Quelle: Adversarial Wronskians: A proof of the Kung–Traub conjecture, https://arxiv.org/abs/2610.40660









