Skolem problem
Finns det en algoritm för att testa om en konstant-rekursiv sekvens har en nolla?
I matematik är Skolem-problemet problemet med att avgöra om värdena för en konstant-rekursiv sekvens inkluderar talet noll. Problemet kan formuleras för återkommande över olika typer av tal, inklusive heltal , rationella tal och algebraiska tal . Det är inte känt om det finns en algoritm som kan lösa detta problem.
En linjär upprepningsrelation uttrycker värdena för en talföljd som en linjär kombination av tidigare värden; till exempel Fibonacci-talen definieras från återfallsrelationen
- F ( n ) = F ( n − 1) + F ( n − 2)
tillsammans med initialvärdena F (0) = 0 och F (1) = 1 . Skolem-problemet är uppkallat efter Thoralf Skolem , på grund av hans papper från 1933 som bevisar Skolem -Mahler-Lech-satsen på nollorna i en sekvens som tillfredsställer en linjär återkomst med konstanta koefficienter . Denna sats säger att om en sådan sekvens har nollor, så upprepas positionerna för nollorna regelbundet med ändligt många undantag. Skolem bevisade detta för återkommande över de rationella siffrorna, och Mahler och Lech utökade det till andra system av siffror . Bevisen för satsen visar dock inte hur man testar om det finns några nollor.
Det finns en algoritm för att testa om en konstant-rekursiv sekvens har oändligt många nollor, och om så är fallet för att konstruera en uppdelning av positionerna för dessa nollor till periodiska delsekvenser, baserat på de algebraiska egenskaperna hos rötterna till det karakteristiska polynomet för det givna upprepning. Den återstående svåra delen av Skolem-problemet är att avgöra om den ändliga uppsättningen av icke-repeterande nollor är tom eller inte.
Partiella lösningar på Skolem-problemet är kända, som täcker det speciella fallet med problemet för återfall av högst fyra grader. Dessa lösningar gäller dock inte för återfall av grad fem eller mer.
För heltalsupprepningar är Skolem-problemet känt för att vara NP-hårt .
Se även
externa länkar
- Tao, Terence (25 maj 2007), "Öppen fråga: effektiv Skolem–Mahler–Lech-sats" , Vad är nytt