Сколемская проблема - Skolem problem

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Есть ли алгоритм, позволяющий проверить, имеет ли постоянно-рекурсивная последовательность ноль?
(больше нерешенных задач по математике)

В математике Сколемская проблема проблема определения того, являются ли значения постоянно-рекурсивная последовательность включить число ноль. Задача может быть сформулирована для повторений над разными типами чисел, включая целые числа, рациональное число, и алгебраические числа. Неизвестно, существует ли алгоритм что может решить эту проблему.[1]

Линейное рекуррентное отношение выражает значения последовательности чисел как линейную комбинацию более ранних значений; например, Числа Фибоначчи может быть определено из рекуррентного соотношения

F(п) = F(п − 1) + F(п − 2)

вместе с начальными значениями F(0) = 0 и F(1) = 1.Сколемская проблема названа в честь Торальф Сколем, из-за его статьи 1933 года, доказывающей Теорема Сколема – Малера – Леха. на нулях последовательности, удовлетворяющей линейной рекуррентности с постоянными коэффициентами.[2] Эта теорема утверждает, что если такая последовательность имеет нули, то, за исключением конечного числа, положения нулей регулярно повторяются. Сколем доказал это для рецидивов над рациональное число, а Малер и Лех распространили его на другие системы чисел. Однако доказательства теоремы не показывают, как проверить, существуют ли нули.

Существует алгоритм для проверки того, имеет ли постоянно-рекурсивная последовательность бесконечное количество нулей, и, если да, для построения разложения позиций этих нулей на периодические подпоследовательности, основываясь на алгебраических свойствах корней характеристического многочлена данного повторение.[3] Оставшаяся трудная часть проблемы Сколема - это определить, является ли конечный набор неповторяющихся нулей пустым или нет.[1]

Известны частные решения проблемы Сколема, покрывающие частный случай проблемы для возвращений степени не выше четвертой. Однако эти решения не применимы к рецидивам пятой степени и более.[1][4][5]

Для целочисленных повторений проблема Сколема известна как NP-жесткий.[6]

Рекомендации

  1. ^ а б c Уакнин, Джоэль; Уоррелл, Джеймс (2012), "Проблемы решения для линейных рекуррентных последовательностей", Проблемы достижимости: 6-й международный семинар, RP 2012, Бордо, Франция, 17–19 сентября 2012 г., Материалы, Конспект лекций по информатике, 7550, Heidelberg: Springer-Verlag, стр. 21–28, Дои:10.1007/978-3-642-33512-9_3, МИСТЕР  3040104.
  2. ^ Сколем, чт. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. акад. Скрифтер, я (6). Уакнин и Уоррелл (2012) вместо этого процитируйте статью Сколема 1934 года для этого результата.
  3. ^ Берстель, Жан; Миньотт, Морис (1976), "Deux propriétés décidables des suites récurrentes linéaires", Bulletin de la Société Mathématique de France (На французском), 104 (2): 175–184, МИСТЕР  0414475.
  4. ^ Mignotte, M .; Шори, Т. Н.; Тийдеман, Р. (1984), «Расстояние между членами алгебраической рекуррентной последовательности», Journal für die Reine und Angewandte Mathematik, 349: 63–76, МИСТЕР  0743965.
  5. ^ Верещагин, Н. К. (1985), "Проблема появления нуля в линейной рекурсивной последовательности", Математические заметки (на русском), 38 (2): 177–189, 347, МИСТЕР  0808885.
  6. ^ Блондель, Винсент Д .; Портье, Наташа (2002), "Наличие нуля в целочисленной линейной рекуррентной последовательности NP-трудно решить", Линейная алгебра и ее приложения, 351/352: 91–98, Дои:10.1016 / S0024-3795 (01) 00466-9, МИСТЕР  1917474.

внешняя ссылка