概要 - 低次のSkolem問題の複雑さについて

タイトル
低次のSkolem問題の複雑さについて

時間
2025-07-15 12:04:28

著者
{"Piotr Bacik","Joël Ouaknine","James Worrell"}

カテゴリ
{cs.CC,cs.LO}

リンク
http://arxiv.org/abs/2507.11234v1

PDF リンク
http://arxiv.org/pdf/2507.11234v1

概要

Skolem問題は、与えられた線形再帰序列（LRS）にゼロ項があるかどうかを問う問題です。この問題は一般的には不決定可能ですが、この論文では、指定された範囲内にゼロ項が存在するかどうかを決定する問題の有限版に対して、ランダム化アルゴリズムを提案しています。このアルゴリズムは、次数がd以下のLRSに対して多項式時間で実行され、それにより、次数が4以下の無制約のSkolem問題がcoRP（多項式時間の認証RAM）に属することを示しています。 このアルゴリズムの鍵は、LRSをp進解析関数Fに拡張し、p進解析学を用いて指数的に大きな範囲内の候補ゼロを探すことです。アルゴリズムは範囲内のすべての余剰mに対して深さ優先探索を行い、各候補ゼロに対して、その項umを表す算術回路を構築し、ランダム多项式時間でゼロかどうかをチェックします。 アルゴリズムの実行時間はLRSの次数の指数関数的に増加しますが、これは有限版Skolem問題のNP難しさによる必要なものです。しかし、固定された次数のLRSに対しても、指数的に大きな範囲内のゼロを検出する必要があるため、p進解析学の使用が必要です。 このアルゴリズムは、SkolemがSkolem-Mahler-Lech定理の元の証明で提案したp進アプローチに基づいています。これは、LRSをp進解析関数Fに拡張し、Fのゼロをp進解析学を用いて探すことです。アルゴリズムはp進冪級数のMahler系列の表現を使用し、p進数で直接計算することなく、基盤となるLRSを扱うことができます。 アルゴリズムの正しさは、Van der PoortenとSchlickeweiによるSkolemの証明の定量的精査に依存しており、これはFのp進体におけるゼロの数の上界を提供します。これにより、アルゴリズムが検討する候補ゼロの数が多項式に制約されることが示されます。また、この結果はWeierstrass準備定理と組み合わせて、p進体において冪級数Fがゼロを持つかどうかを多項式時間で決定するために使用されます。 結論として、この論文は、次数がd以下のLRSに対して多項式時間で実行されるランダム化アルゴリズムを提案し、次数が4以下の無制約のSkolem問題がcoRPに属することを示しています。問題のNP難しさによる必要なため、アルゴリズムの複雑性はLRSの次数の指数関数的に増加します。


推奨論文

夢：インタラクティブな世界生成モデル

無限群の隠れた部分群問題

視覚と言語のトレーニングは分類学的知識の展開を助けますが、それを根本的に変えるものではありません

PINNsと画像分類のための動的学習率スケジュールを用いた神経ネットワークトレーニングの改善

非曲がり可能なガラス中間基板によって実現される高性能かつ熱的にも可能なマルチチップレットアーキテクチャの設計

トレースノルム収縮係数の計算的側面

亀裂部の間に落ちる：分断された脆い亀裂前縁におけるエネルギー貯蔵

深層脳ネット：エッフェクティブネットB0とResNet50を使用した、移行学習を通じてMRI画像における脳腫瘍検出のための最適化された深層学習モデル

時砂並べ：新しい並列ソートアルゴリズムとその実装

ApexOracleを使って、将来の病原体に対する抗生物質を予測および生成することを日本語に翻訳すると以下のようになります： ApexOracleを使って、将来の病原体に対する抗生物質を予測・生成する