http://dbpedia.org/ontology/abstract
|
In mathematics, the Skolem problem is the … In mathematics, the Skolem problem is the problem of determining whether the values of a constant-recursive sequence include the number zero. The problem can be formulated for recurrences over different types of numbers, including integers, rational numbers, and algebraic numbers. It is not known whether there exists an algorithm that can solve this problem. A linear recurrence relation expresses the values of a sequence of numbers as a linear combination of earlier values; for instance, the Fibonacci numbers may be defined from the recurrence relation F(n) = F(n − 1) + F(n − 2) together with the initial values F(0) = 0 and F(1) = 1.The Skolem problem is named after Thoralf Skolem, because of his 1933 paper proving the Skolem–Mahler–Lech theorem on the zeros of a sequence satisfying a linear recurrence with constant coefficients. This theorem states that, if such a sequence has zeros, then with finitely many exceptions the positions of the zeros repeat regularly. Skolem proved this for recurrences over the rational numbers, and Mahler and Lech extended it to other systems of numbers. However, the proofs of the theorem do not show how to test whether there exist any zeros. There does exist an algorithm to test whether a constant-recursive sequence has infinitely many zeros, and if so to construct a decomposition of the positions of those zeros into periodic subsequences, based on the algebraic properties of the roots of the characteristic polynomial of the given recurrence. The remaining difficult part of the Skolem problem is determining whether the finite set of non-repeating zeros is empty or not. Partial solutions to the Skolem problem are known, covering the special case of the problem for recurrences of degree at most four. However, these solutions do not apply to recurrences of degree five or more. For integer recurrences, the Skolem problem is known to be NP-hard.the Skolem problem is known to be NP-hard.
, スコーレム問題とは、定数係数回帰数列(constant-recursive sequ … スコーレム問題とは、定数係数回帰数列(constant-recursive sequence)に 0 が含まれるかを判定する数学上の問題である。この問題は、整数、有理数、代数的数など、さまざまな種類の数に対して定式化される。この問題を解くアルゴリズムが存在するかは未解決である。 線形回帰関係は、各項をそれ以前の項の線形結合として定義し、例えば、フィボナッチ数は、以下の漸化式 F(n) = F(n − 1) + F(n − 2) と初期値 F(0) = 0、F(1) =1で定義される。スコーレム問題は1933年に数列上の 0 についてのを証明したトアルフ・スコーレムにちなんで名付けられた。この定理は、数列に 0 が含まれる場合、非常に多くの例外を除いて、0 は規則的に繰り返されるという定理である。スコーレムはこれを有理数上の回帰数列について証明し、は代数的数上で、レッヒは標数が 0 の体で成り立つことを証明した。 しかし、定理の証明は、0 が存在するかどうかを判断する方法を示していない。 定数係数回帰数列が無限に多くの 0 を含むかを判断するアルゴリズムは存在し、もし無限に多くの 0 を含むのであれば、漸化式の特性多項式の根の代数的性質に基づいて、0 の位置の「分解」を周期的な部分列として示すことができる。スコーレム問題の難しい部分は、0 が有限個である(したがって周期的でない)場合に、0 が存在するかを判定する部分である。 スコーレム問題に対する部分的な解は知られており、4項以下の漸化式の特殊な場合については解かれている。しかし、この解決法は5項以上の漸化式には適用できない。 整数回帰におけるスコーレム問題はNP困難に属する。項以上の漸化式には適用できない。 整数回帰におけるスコーレム問題はNP困難に属する。
, En mathématiques, et plus particulièrement … En mathématiques, et plus particulièrement en théorie des nombres, le problème des Skolem est le problème de déterminer s'il existe, parmi les éléments d'une suite récurrente linéaire à coefficients constants, un terme qui est nul. Le problème peut être formulé pour divers types de nombres, y compris les entiers relatifs, les nombres rationnels, et les nombres algébriques. Il n'est pas connu s'il existe un algorithme qui permet de résoudre ce problème.rithme qui permet de résoudre ce problème.
|
http://dbpedia.org/ontology/wikiPageExternalLink
|
https://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/%7Cfirst=Terence%7Clast=Tao%7Cauthorlink=Terence +
|
http://dbpedia.org/ontology/wikiPageID
|
48160075
|
http://dbpedia.org/ontology/wikiPageLength
|
5008
|
http://dbpedia.org/ontology/wikiPageRevisionID
|
1096307593
|
http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Category:Unsolved_problems_in_mathematics +
, http://dbpedia.org/resource/Rational_number +
, http://dbpedia.org/resource/Algebraic_number +
, http://dbpedia.org/resource/Algorithm +
, http://dbpedia.org/resource/Constant-recursive_sequence +
, http://dbpedia.org/resource/Fibonacci_number +
, http://dbpedia.org/resource/Thoralf_Skolem +
, http://dbpedia.org/resource/NP-hard +
, http://dbpedia.org/resource/Integer +
, http://dbpedia.org/resource/Category:Recurrence_relations +
, http://dbpedia.org/resource/Skolem%E2%80%93Mahler%E2%80%93Lech_theorem +
|
http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Unsolved +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Reflist +
|
http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Recurrence_relations +
, http://dbpedia.org/resource/Category:Unsolved_problems_in_mathematics +
|
http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Problem +
|
http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Skolem_problem?oldid=1096307593&ns=0 +
|
http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Skolem_problem +
|
owl:sameAs |
http://dbpedia.org/resource/Skolem_problem +
, http://ja.dbpedia.org/resource/%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%AC%E3%83%A0%E5%95%8F%E9%A1%8C +
, http://www.wikidata.org/entity/Q25304237 +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_de_Skolem +
, https://global.dbpedia.org/id/2NzSq +
|
rdf:type |
http://dbpedia.org/ontology/Disease +
|
rdfs:comment |
In mathematics, the Skolem problem is the … In mathematics, the Skolem problem is the problem of determining whether the values of a constant-recursive sequence include the number zero. The problem can be formulated for recurrences over different types of numbers, including integers, rational numbers, and algebraic numbers. It is not known whether there exists an algorithm that can solve this problem. A linear recurrence relation expresses the values of a sequence of numbers as a linear combination of earlier values; for instance, the Fibonacci numbers may be defined from the recurrence relation F(n) = F(n − 1) + F(n − 2)rrence relation F(n) = F(n − 1) + F(n − 2)
, En mathématiques, et plus particulièrement … En mathématiques, et plus particulièrement en théorie des nombres, le problème des Skolem est le problème de déterminer s'il existe, parmi les éléments d'une suite récurrente linéaire à coefficients constants, un terme qui est nul. Le problème peut être formulé pour divers types de nombres, y compris les entiers relatifs, les nombres rationnels, et les nombres algébriques. Il n'est pas connu s'il existe un algorithme qui permet de résoudre ce problème.rithme qui permet de résoudre ce problème.
, スコーレム問題とは、定数係数回帰数列(constant-recursive sequ … スコーレム問題とは、定数係数回帰数列(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困難に属する。項以上の漸化式には適用できない。 整数回帰におけるスコーレム問題はNP困難に属する。
|
rdfs:label |
Problème de Skolem
, スコーレム問題
, Skolem problem
|