スコーレム問題とは - わかりやすく解説 Weblio辞書

スコーレム問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/05 02:03 UTC 版)

スコーレム問題とは、定数係数回帰数列（constant-recursive sequence）に 0 が含まれるかを判定する数学上の問題である。この問題は、整数、有理数、代数的数など、さまざまな種類の数に対して定式化される。この問題を解くアルゴリズムが存在するかは未解決である^[1]。

^ 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, 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, MR 3040104
^ Skolem, Th. (1933), “Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen”, Oslo Vid. akad. Skrifter I (6)
^ Berstel, Jean; Mignotte, Maurice (1976), “Deux propriétés décidables des suites récurrentes linéaires” (French), Bulletin de la Société Mathématique de France 104 (2): 175–184, MR 0414475
^ 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 743965
^ Vereshchagin, N. K. (1985), “The problem of the appearance of a zero in a linear recursive sequence” (Russian), Matematicheskie Zametki 38 (2): 177–189, 347, MR 808885
^ 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

「スコーレム問題」の続きの解説一覧

このページでは「ウィキペディア」からスコーレム問題を検索した結果を表示しています。
Weblioに収録されているすべての辞書からスコーレム問題を検索する場合は、下記のリンクをクリックしてください。