스콜렘 문제

Skolem problem
수학의 미해결 문제:

일정한 반복 시퀀스에 0이 있는지 여부를 테스트할 알고리즘이 있는가?

(수학에서 더 풀리지 않은 문제)

수학에서 스콜렘 문제는 일정한 반복수열의 값이 숫자 0을 포함하는지 여부를 결정하는 문제다.이 문제는 정수, 합리적 수, 대수적 숫자를 포함한 다른 유형의 숫자에 대한 반복에 대해 공식화될 수 있다.이 문제를 해결할 수 있는 알고리즘이 존재하는지 여부는 알려지지 않았다.[1]

선형 재발 관계는 일련의 숫자 값을 이전 값의 선형 결합으로 표현한다. 예를 들어, 피보나치 숫자는 재발 관계에서 정의될 수 있다.

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

초기 값 F(0) = 0, F(1) = 1. 스콜렘 문제는 일정한 계수로 선형 재발을 만족하는 수열의 0에 대해 스콜렘-마흘러-레흐 정리를 증명하는 그의 1933년 논문 때문에 소랄프 스콜렘의 이름을 따서 명명되었다.[2]이 정리는 그러한 시퀀스에 0이 있으면, 0의 위치가 정확히 많은 예외를 제외하고는 규칙적으로 반복된다고 기술하고 있다.스콜렘은 합리적인 숫자에 대한 재발로 이것을 증명했고, 말러와 레흐는 그것을 다른 숫자의 체계로 확장시켰다.그러나 정리의 증명들은 0이 존재하는지 여부를 어떻게 시험해야 하는지를 보여주지 않는다.

일정한 반복 시퀀스에 0이 무한히 많은지 여부를 시험하는 알고리즘이 존재하며, 만약 그렇다면 해당 0의 위치를 주기적인 반복으로 분해하는 것을 구성하기 위해 주어진 반복의 특성 다항식의 뿌리에 대한 대수적 특성에 기초한다.[3]스콜렘 문제의 남은 어려운 부분은 유한 집합의 비반복 0이 비어 있는지 여부를 결정하는 것이다.[1]

스콜렘 문제에 대한 부분적인 해결책이 알려져 있으며, 최대 4개의 등급이 재발하는 문제에 대한 특수한 경우를 다루고 있다.그러나 이러한 해결책은 5급 이상의 반복에는 적용되지 않는다.[1][4][5]

정수 재귀의 경우 스콜렘 문제는 NP-hard로 알려져 있다.[6]

참고 항목

참조

  1. ^ a b c Ouaknine, Joël; Worrell, James (2012), "Decision problems for linear recurrence sequences", Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, MR 3040104.
  2. ^ Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akad. Skrifter, I (6). 와크나인 & 월렐 (2012)은 대신에 이 결과에 대해 1934년 스콜렘의 논문을 인용한다.
  3. ^ Berstel, Jean; Mignotte, Maurice (1976), "Deux propriétés décidables des suites récurrentes linéaires", Bulletin de la Société Mathématique de France (in French), 104 (2): 175–184, doi:10.24033/bsmf.1823, MR 0414475.
  4. ^ Mignotte, M.; Shorey, T. N.; Tijdeman, R. (1984), "The distance between terms of an algebraic recurrence sequence", Journal für die Reine und Angewandte Mathematik, 349: 63–76, MR 0743965.
  5. ^ Vereshchagin, N. K. (1985), "The problem of the appearance of a zero in a linear recursive sequence", Matematicheskie Zametki (in Russian), 38 (2): 177–189, 347, MR 0808885.
  6. ^ Blondel, Vincent D.; Portier, Natacha (2002), "The presence of a zero in an integer linear recurrent sequence is NP-hard to decide", Linear Algebra and Its Applications, 351/352: 91–98, doi:10.1016/S0024-3795(01)00466-9, MR 1917474.

외부 링크