Jump to content

Школьная проблема

Нерешенная задача по математике :
Существует ли алгоритм проверки того, имеет ли константно-рекурсивная последовательность ноль?

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

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

F ( п ) знак равно F ( п - 1) + F ( п - 2)

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

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

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

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

См. также

[ редактировать ]
  1. ^ Перейти обратно: а б с Уакнин, Жоэль; Уоррелл, Джеймс (2012), «Проблемы принятия решений для линейных рекуррентных последовательностей», Проблемы достижимости: 6-й международный семинар, RP 2012, Бордо, Франция, 17–19 сентября 2012 г., Труды , Конспекты лекций по информатике, том. 7550, Гейдельберг: Springer-Verlag, стр. 21–28, номер документа : 10.1007/978-3-642-33512-9_3 , MR   3040104 .
  2. ^ Сколем, Т. (1933), «Некоторые теоремы о некоторых разложениях в ряд и экспоненциальных соотношениях с применением к диофантовым уравнениям», Осло Вид. Академический Срифтер , я (6) . Вместо этого Оуакнин и Уоррелл (2012) цитируют статью Скулема 1934 года, подтверждающую этот результат.
  3. ^ Берстель, Жан; Миньотт, Морис (1976), «Два разрешимых свойства линейных повторяющихся последовательностей» , Bulletin de la Société Mathématique de France (на французском языке), 104 (2): 175–184, doi : 10.24033/bsmf.1823 , MR   0414475 .
  4. ^ Миньотт, М.; Шори, Теннесси ; Тайдеман, Р. (1984), «Расстояние между членами алгебраической рекуррентной последовательности», Журнал чистой и прикладной математики , 349 : 63–76, MR   0743965 .
  5. ^ Верещагин, Н.К. (1985), "Проблема появления нуля в линейно-рекурсивной последовательности", Математические заметки , 38 (2): 177–189, 347, МР   0808885 .
  6. ^ Блондель, Винсент Д.; Портье, Наташа (2002), «Наличие нуля в целочисленной линейной рекуррентной последовательности определить NP-трудно», Линейная алгебра и ее приложения , 351/352: 91–98, doi : 10.1016/S0024-3795 (01 )00466-9 , МР   1917474 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 1f254df709b5d1a9bf5ca1b67c5a2519__1674062280
URL1:https://arc.ask3.ru/arc/aa/1f/19/1f254df709b5d1a9bf5ca1b67c5a2519.html
Заголовок, (Title) документа по адресу, URL1:
Skolem problem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)