About: スコーレム問題

スコーレム問題とは、定数係数回帰数列（constant-recursive sequence）に 0 が含まれるかを判定する数学上の問題である。この問題は、整数、有理数、代数的数など、さまざまな種類の数に対して定式化される。この問題を解くアルゴリズムが存在するかは未解決である。 線形回帰関係は、各項をそれ以前の項の線形結合として定義し、例えば、フィボナッチ数は、以下の漸化式 F(n) = F(n − 1) + F(n − 2) と初期値 F(0) = 0、F(1) =1で定義される。スコーレム問題は1933年に数列上の 0 についてのを証明したトアルフ・スコーレムにちなんで名付けられた。この定理は、数列に 0 が含まれる場合、非常に多くの例外を除いて、0 は規則的に繰り返されるという定理である。スコーレムはこれを有理数上の回帰数列について証明し、は代数的数上で、レッヒは標数が 0 の体で成り立つことを証明した。 しかし、定理の証明は、0 が存在するかどうかを判断する方法を示していない。 スコーレム問題に対する部分的な解は知られており、4項以下の漸化式の特殊な場合については解かれている。しかし、この解決法は5項以上の漸化式には適用できない。 整数回帰におけるスコーレム問題はNP困難に属する。