数学において、スコーレム問題とは、定数再帰列の値に零が含まれるかどうかを判定する問題である。この問題は、整数、有理数、代数的数など、様々な種類の数に対する再帰式について定式化できる。この問題を解くアルゴリズムが存在するかどうかは知られていない。 [1]
線形再帰関係は、一連の数値の値を、それ以前の数値の線形結合として表現する。例えば、フィボナッチ数は、再帰関係から定義することができる。
- F ( n ) = F ( n − 1 ) + F ( n − 2 )
初期値F (0) = 0およびF (1) = 1とともに。スコーレム問題は、定数係数の線型回帰を満たす数列の零点に関するスコーレム・マーラー・レヒの定理を証明した1933 年の論文にちなんで、トラルフ・スコーレムにちなんで名付けられました。[2]この定理は、そのような数列に零点がある場合、有限回の例外を除いて零点の位置が規則的に繰り返されることを述べています。スコーレムは有理数上の回帰についてこれを証明し、マーラーとレヒはそれを他の数体系に拡張しました。しかし、定理の証明では零点が存在するかどうかをテストする方法は示されていません。
定数再帰列に無限個の零点が存在するかどうかを判定し、もし存在するならば、与えられた再帰の特性多項式の根の代数的性質に基づいて、それらの零点の位置を周期的な部分列に分解するアルゴリズムが存在する。 [3]スコーレム問題の残りの難しい部分は、繰り返されない零点の有限集合が空であるかどうかを判断することである。[1]
スコーレム問題の部分解は知られており、これは最大4次までの回帰問題に関する特殊なケースをカバーしている。しかし、これらの解は5次以上の回帰問題には適用できない。[1] [4] [5]
整数再帰の場合、スコーレム問題はNP困難であることが知られています。[6]
参照
参考文献
- ^ abc Ouaknine, Joël; Worrell, James (2012)、「線形再帰シーケンスの決定問題」、到達可能性問題：第6回国際ワークショップ、RP 2012、フランス、ボルドー、2012年9月17～19日、議事録、コンピュータサイエンスの講義ノート、第7550巻、ハイデルベルク：Springer-Verlag、pp. 21～ 28、doi :10.1007/978-3-642-33512-9_3、ISBN 978-3-642-33511-2、MR 3040104。
- ^ スコレム、Th. (1933)、「Einige Sätze über gewisse Reihenentwicklungen undexponentiale Beziehungen mit Anwendung auf diophantische Gleichungen」、オスロ ヴィッド。アカド。スクリフター、私(6)Ouaknine & Worrell (2012)は、この結果について、代わりにSkolemの1934年の論文を引用している。
- ^ ジャン・ベルステル; Mignotte、Maurice (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、doi : 10.24033/bsmf.1823、MR 0414475。
- ^ ミニョット、M.ショーリー, テネシー州; Tijdeman, R. (1984)、「代数漸化列の項間の距離」、Journal für die Reine und Angewandte Mathematik、349 : 63–76、MR 0743965。
- ^ Vereshchagin, NK (1985)、「線形再帰列におけるゼロの出現の問題」、Matematicheskie Zametki（ロシア語）、38（2）：177–189、347、MR 0808885。
- ^ Blondel, Vincent D.; Portier, Natacha (2002)、「整数線形回帰列における零点の存在はNP困難であると判定される」、線形代数とその応用、351/352: 91– 98、doi :10.1016/S0024-3795(01)00466-9、MR 1917474。
外部リンク
- タオ、テレンス（2007年5月25日）「未解決問題：有効なスコーレム・マーラー・レヒ定理」、新着情報
