Zusammenfassung - Über die Komplexität des Skolemproblems bei niedrigen Ordnungen

Über die Komplexität des Skolemproblems bei niedrigen Ordnungen

2025-07-15 12:04:28

{"Piotr Bacik","Joël Ouaknine","James Worrell"}

{cs.CC,cs.LO}

Das Skolem-Problem fragt, ob eine gegebene lineare Recurrencesequenz (LRS) einen Nullterm hat. Obwohl das Problem im Allgemeinen unentscheidbar ist, präsentiert das Papier einen zufälligen Algorithmus für eine begrenzte Version des Problems, der bestimmt, ob es innerhalb eines angegebenen Bereichs einen Nullterm gibt. Dieser Algorithmus läuft in Polynomzeit für LRS von Ordnung bis zu d und zeigt als Korollar, dass das unbeschränkte Skolem-Problem für LRS von Ordnung bis zu 4 in coRP (certified RAM mit Polynomzeit) liegt. Der Schlüssel zum Algorithmus liegt in der Erweiterung der LRS zu einer p-adischen analytischen Funktion F und der Verwendung der p-adischen Analyse, um Kandidaten für Nullstellen innerhalb eines exponentiell großen Bereichs zu finden. Der Algorithmus führt eine tiefenorientierte Suche nach allen Resten m innerhalb des Bereichs durch und konstruiert für jede Kandidatennullstelle einen arithmetischen Schaltkreis, der den Term um darstellt, und überprüft in zufälliger Polynomzeit auf Zerohäufigkeit. Die Laufzeit des Algorithmus ist exponentiell in der Ordnung der LRS, was aufgrund der NP-Hardness des begrenzten Skolem-Problems notwendig ist. Allerdings beinhaltet das Problem auch für LRS einer festen Ordnung, die Erkennung von Nullstellen innerhalb eines exponentiell großen Bereichs, was die Verwendung der p-adischen Analyse erfordert. Der Algorithmus basiert auf einem p-adischen Ansatz, den Skolem in seiner ursprünglichen Beweismethode für das Skolem-Mahler-Lech-Theorem eingeführt hat. Dies beinhaltet die Erweiterung der LRS zu einer p-adischen analytischen Funktion F und die Verwendung der p-adischen Analyse, um Nullstellen von F zu finden. Der Algorithmus nutzt die Mahler-Reihe-Repräsentation von p-adischen Potenzreihen, was es ermöglicht, mit der zugrunde liegenden LRS zu arbeiten, ohne direkt mit p-adischen Zahlen zu rechnen. Die Richtigkeit des Algorithmus beruht auf einer quantitativen Feinabstimmung von Skolems Beweis, die von Van der Poorten und Schlickewei vorgeschlagen wurde. Dieses Ergebnis bietet eine Obergrenze für die Anzahl der Nullstellen von F im p-adischen Körper, was sich in eine polynomiale Begrenzung der Anzahl der geprüften Kandidatennullstellen durch den Algorithmus übersetzt. Zusätzlich wird dieses Ergebnis in Kombination mit dem Weierstraß-Vorbereitungssatz verwendet, um in Polynomzeit zu bestimmen, ob die Potenzreihe F einen Nullterm im p-adischen Körper hat. Zusammenfassend präsentiert das Papier einen zufälligen Algorithmus für das begrenzte Skolem-Problem, der in Polynomzeit für LRS von Ordnung bis zu d läuft, und zeigt, dass das unbeschränkte Skolem-Problem für LRS von Ordnung bis zu 4 in coRP liegt. Die Komplexität des Algorithmus ist exponentiell in der Ordnung der LRS, was aufgrund der NP-Hardness des Problems notwendig ist.