Школьная проблема
В математике — проблема Сколема это проблема определения того, включают ли значения константно-рекурсивной последовательности число ноль. Проблему можно сформулировать для рекурсий над различными типами чисел, включая целые , рациональные и алгебраические числа . Неизвестно, существует ли алгоритм , способный решить эту проблему. [1]
Линейное рекуррентное отношение выражает значения последовательности чисел как линейную комбинацию предыдущих значений; например, числа Фибоначчи могут быть определены из рекуррентного соотношения
- F ( п ) знак равно F ( п - 1) + F ( п - 2)
вместе с начальными значениями F (0)=0 и F (1)=1 .Проблема Скулема названа в честь Торальфа Скулема из-за его статьи 1933 года, доказывающей теорему Скулема-Малера-Леха о нулях последовательности, удовлетворяющей линейной рекуррентности с постоянными коэффициентами . [2] Эта теорема утверждает, что если такая последовательность имеет нули, то за конечным числом исключений положения нулей регулярно повторяются. Скулем доказал это для возвратов над рациональными числами, а Малер и Лех распространили это на другие системы чисел . Однако доказательства теоремы не показывают, как проверить, существуют ли нули.
Существует алгоритм, позволяющий проверить, имеет ли константно-рекурсивная последовательность бесконечное число нулей, и если да, то построить разложение положений этих нулей на периодические подпоследовательности, основанный на алгебраических свойствах корней характеристического многочлена данной рецидив. [3] или нет конечное множество неповторяющихся нулей Оставшаяся трудная часть проблемы Скулема — определить, пусто . [1]
Известны частичные решения задачи Скулема, охватывающие частный случай задачи для рекуррентностей степени не выше четвертой. Однако эти решения не применимы к рецидивам пятой степени и выше. [1] [4] [5]
Для целочисленных повторений задача Скулема известна как NP-трудная . [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Уакнин, Жоэль; Уоррелл, Джеймс (2012), «Проблемы принятия решений для линейных рекуррентных последовательностей», Проблемы достижимости: 6-й международный семинар, RP 2012, Бордо, Франция, 17–19 сентября 2012 г., Труды , Конспекты лекций по информатике, том. 7550, Гейдельберг: Springer-Verlag, стр. 21–28, номер документа : 10.1007/978-3-642-33512-9_3 , MR 3040104 .
- ^ Сколем, Т. (1933), «Некоторые теоремы о некоторых разложениях в ряд и экспоненциальных соотношениях с применением к диофантовым уравнениям», Осло Вид. Академический Срифтер , я (6) . Вместо этого Оуакнин и Уоррелл (2012) цитируют статью Скулема 1934 года, подтверждающую этот результат.
- ^ Берстель, Жан; Миньотт, Морис (1976), «Два разрешимых свойства линейных повторяющихся последовательностей» , Bulletin de la Société Mathématique de France (на французском языке), 104 (2): 175–184, doi : 10.24033/bsmf.1823 , MR 0414475 .
- ^ Миньотт, М.; Шори, Теннесси ; Тайдеман, Р. (1984), «Расстояние между членами алгебраической рекуррентной последовательности», Журнал чистой и прикладной математики , 349 : 63–76, MR 0743965 .
- ^ Верещагин, Н.К. (1985), "Проблема появления нуля в линейно-рекурсивной последовательности", Математические заметки , 38 (2): 177–189, 347, МР 0808885 .
- ^ Блондель, Винсент Д.; Портье, Наташа (2002), «Наличие нуля в целочисленной линейной рекуррентной последовательности определить NP-трудно», Линейная алгебра и ее приложения , 351/352: 91–98, doi : 10.1016/S0024-3795 (01 )00466-9 , МР 1917474 .
Внешние ссылки
[ редактировать ]- Тао, Теренс (25 мая 2007 г.), «Открытый вопрос: эффективная теорема Скулема – Малера – Леха» , Что нового