Das Skolem-Problem ist eine Problemstellung der Mathematik und der theoretischen Informatik, die fragt, ob eine gegebene ganzzahlige lineare Rekursionsfolge eine Nullstelle besitzt. Das zugehörige Entscheidungsproblem, ob ein Algorithmus existiert, der diese Frage für alle linearen Rekursionsfolgen entscheiden kann, ist offen.
Das Problem ist nach Thoralf Skolem benannt, der 1934 erste Resultate über die Struktur der Nullstellen solcher Folgen erzielte. Der Satz von Skolem-Mahler-Lech macht eine Aussage dazu.
Skolem-Problem Eine Folge mit heißt lineare Rekursionsfolge (LRF), wenn sie für alle eine Rekursion der Form
mit festen Koeffizienten erfüllt. Man nennt die Ordnung der Folge.
Beispiele: die Fibonacci-Folge erfüllt und hat Ordnung .
Formulierung des Problems Das Skolem-Problem lautet: Gegeben eine lineare Rekursionsfolge , gibt es ein , so dass ? Das zugehörige Entscheidungsproblem ist offen: Gibt es einen Algorithmus, der für jede beliebigen lineare Rekursionsfolge das Skolem-Problem löst?
Erläuterungen Der Algorithmus, der schaut, ob irgendwann ein Folgenglied der unendlichen Rekursionsfolge gleich Null ist, ist kein Entscheidungsverfahren, da er im Fall, dass keine Nullstelle existiert, nie terminiert. Gesucht ist ein Algorithmus , der für eine lineare Rekursionsfolge die Entscheidungsfunktion
berechnet, das heißt .
Bekannte Resultate Satz von Skolem-Mahler-Lech und seine Varianten Der Satz von Skolem-Mahler-Lech sagt Die Menge der Nullstellen einer linearen Rekursionsfolge ist die Vereinigung einer endlichen Menge und einer endlichen Anzahl von arithmetischen Folgen. Er liefert jedoch keinen Algorithmus zur Entscheidung, ob überhaupt Nullstellen existieren.
Eine stärkere Variante gilt für nicht-degenerierte Rekursionsfolgen. Eine lineare Rekursionsfolge heißt nicht-degeneriert, wenn der Quotient zweier verschiedener Nullstellen ihres charakteristischen Polynoms keine Einheitswurzel ist. Eine nicht-degenerierte lineare Rekursionsfolge hat nur endlich viele Nullstellen. Es ist jedoch offen, wie man die Nullstellenmenge allgemein berechnet.
Eine lineare Rekursionsfolge heißt einfach, wenn ihr charakteristisches Polynoms nur paarweise verschiedene Nullstellen besitzt. Für einfache LRF wurde 2022 ein Verfahren gefunden, welche das Skolem-Problem entscheidet, aber unter der Bedingung, dass zwei offene Vermutungen aus der analytische Zahlentheorie wahr sind (die p-adische Schanuel-Vermutung und das exponential local-global principle).
Weitere Resultate 1984/1985 wurde gezeigt, dass das Problem für Rekursionen bis zur Ordnung entscheidbar ist.Tijdeman, R., Mignotte, M., and Shorey, T.N. "The distance between terms of an algebraic recurrence sequence.." Journal für die reine und angewandte Mathematik 349 (1984): 63-76. Das ist der letzte Stand. Es ist bekannt, dass das Problem NP-schwer ist.
Verwandte Probleme Das Positivitätsproblem fragt, ob alle Folgenglieder nichtnegativ sind: Gegeben eine lineare Rekursionsfolge , gilt dann für alle ? Das Entscheidungsproblem dazu ist auch offen: Gibt es einen Algorithmus, der für jede lineare Rekursionsfolge bestimmt, ob für alle gilt?
Einzelnachweise
Kategorie:Zahlentheorie Kategorie:Rekursion Kategorie:Theoretische Informatik