Parametrized complexity of relations between multidimensional subshifts

1. 問題設定 (Problem)

従来の研究（Jeandel と Vanier, 2014）では、2 つのサブシフト $X$ と $Y$ を両方とも入力として受け取り、それらの関係（$X=Y, X \simeq Y, X \subseteq Y, X \hookrightarrow Y$ など）を判定する問題の複雑性を扱ってきました。これらは一般的に決定不能（undecidable）または非常に高い計算複雑性を持ちます。

本研究では、パラメータ化されたバージョンを扱います。

• パラメータ ($Y$): 事前に固定されたサブシフト。
• 入力 ($X$): 判定対象となるサブシフト（SFT または有効サブシフト）。

目的:
固定されたパラメータ $Y$ の動的性質（周期性、最小性、有限型であることなど）が、入力 $X$ に対する関係判定問題の計算複雑性にどのような影響を与えるかを明らかにすることです。特に、「$Y$ がどのような性質を持てば問題が決定可能になるか（あるいは逆に最も難しくなるか）」を特徴づけることを目指しています。

2. 手法と予備知識 (Methodology & Preliminaries)

• 対象領域: $d$ 次元格子 $\mathbb{Z}^d$ 上のサブシフト。
  • SFT (Subshift of Finite Type): 有限個の禁止パターンで定義される。
  • 有効サブシフト (Effective Subshift): 再帰的に列挙可能な禁止パターンで定義される（$\Sigma^0_1$ 集合）。
• 判定問題:
  • 等号 ($X = Y$)、共役 ($X \simeq Y$)、包含 ($X \subseteq Y, Y \subseteq X$)、埋め込み ($X \hookrightarrow Y, Y \hookrightarrow X$)。
• 複雑性クラス:
  • 算術階層 ($\Sigma^0_1, \Pi^0_1, \Sigma^0_2, \Pi^0_2, \Sigma^0_3$) や、その差集合 $D(\Sigma^0_1)$ を用いて問題を分類。
  • 標準的な決定不能問題（Halt, Total, COF, Domino Problem）への帰着（reduction）を用いて下限を示す。
• 主要な道具:
  • Berger 性質: SFT の動的性質が $\Sigma^0_1$-困難であることを示すための枠組み。
  • チューリング機械のシミュレーション: 高次元 SFT における計算能力（ドミノ問題の未決定性）を利用した構成。
  • リフト (Lift): 1 次元の結果を高次元へ拡張する手法。

3. 主要な貢献と結果 (Key Contributions & Results)

著者らは、パラメータ $Y$ の性質と入力 $X$ のクラス（SFT または有効）の組み合わせに応じて、複雑性が劇的に変化することを示しました。

A. 包含問題 ($Y \subseteq X$)

• SFT 入力の場合:
  • 任意の $Y$ に対して、この問題は $L(Y)^c$（$Y$ の言語の補集合）の列挙と同値です。
  • 結果: $Y$ の言語が計算可能（computable）な場合のみ決定可能です。
  • $d \ge 2$ において、SFT の言語のチューリング次数はすべての計算可能列挙次数（c.e. degrees）に及びます。
• 有効入力の場合:
  • 最大複雑性 $\Pi^0_2$-完全を達成する $Y$（SFT ではない有効サブシフト）が存在します。

B. 埋め込み問題 ($Y \hookrightarrow X$)

• SFT 入力の場合:
  • 一般的には $\Sigma^0_1$-困難ですが、$Y$ が有限サブシフト（すべての配置が強く周期的）であれば決定可能です。
  • 驚くべき発見: $Y \hookrightarrow X$ が決定可能であっても、$Y \subseteq X$ が決定不可能（$L(Y)$ が計算不可能）であるような有効サブシフト $Y$ が存在します。これは、包含問題よりも埋め込み問題の方が「簡単」になり得ることを示しています。
  • 最小性を持たない特定の SFT（例：Robinson SFT）では $\Sigma^0_1$-完全になります。
• 有効入力の場合:
  • 常に $\Pi^0_1$-困難（決定不能）です。

C. 逆包含・逆埋め込み ($X \subseteq Y, X \hookrightarrow Y$)

• パラメータ $Y$ が有効サブシフトの場合:
  • $X \subseteq Y$ は $\Pi^0_2$-完全、$X \hookrightarrow Y$ は $\Sigma^0_3$-完全の上限を持ちます。
  • これらの上限に達する具体的な $Y$ の構成を示しました。
  • 例外: $Y$ が有限個の SFT のみを含む場合、両問題とも $\Sigma^0_1$-完全（決定可能）になります。

D. 等号問題 ($X = Y$)

• SFT 入力: $Y$ が SFT なら $\Sigma^0_1$-完全。
• 有効入力:
  • 一般には $\Pi^0_2$-完全ですが、$Y$ が SFT かつ言語が計算可能であれば、複雑性は $D(\Sigma^0_1)$（$\Sigma^0_1$ とその補集合の差）に低下します。
  • 1 次元において、有効サブシフト間の等号問題の複雑性は、$Y$ が SFT かどうかを完全に特徴づけます（SFT なら $D(\Sigma^0_1)$-完全、そうでなければ $\Pi^0_2$-完全）。

E. 共役問題 ($X \simeq Y$)

• SFT 入力: 常に $\Sigma^0_1$-完全。
• 有効入力:
  • 一般には $\Sigma^0_3$-完全ですが、パラメータ $Y$ の性質によって低下します。
  • 重要な結果: $Y$ が「$\Pi^0_1$ 共役不変性質に対して最小（minimal）」である場合（例：全シフト、有限サブシフト、最小サブシフト）、問題の複雑性は $D(\Sigma^0_1)$-完全に低下します。
  • 反例: 言語が計算可能な SFT であっても、その「最小性」を定義する性質が共役不変ではない場合、複雑性は $\Sigma^0_3$-完全のままです。これは、共役不変な性質の存在が計算複雑性の低下に必須であることを示唆しています。

F. 1 次元と高次元の関係

• 1 次元 SFT における埋め込み問題の決定可能性は、高次元へのリフト（lift）を通じて高次元 SFT の決定可能性にも影響します。
• 1 次元の混合（mixing）SFT における共役問題は、埋め込み問題に帰着されます（Krieger の埋め込み定理に基づく）。

4. 意義と結論 (Significance & Conclusion)

1. 決定不能性の「沼」の限界の明確化:
   Rice 定理の類似定理により、SFT の多くの性質は決定不能であることが知られていますが、パラメータ化アプローチにより、特定の条件下（例：$Y$ が有限、または $Y$ が特定の最小性を持つ）では非自明な決定可能問題が存在することを示しました。

2. 動的性質と計算複雑性の深い関連:
   周期性、最小性、有限型性といった動的性質が、計算問題の難しさを直接制御することを定量的に示しました。特に、共役不変な性質と計算可能性の関係は、サブシフトの構造理論において新しい洞察を提供しています。

3. 問題間の非対称性:
   包含問題と埋め込み問題、あるいは $X \subseteq Y$ と $Y \subseteq X$ の間で、パラメータ $Y$ の性質に対する依存関係が非対称であることを発見しました。これは、従来の「2 入力問題」の視点では見えなかった微細な構造を浮き彫りにしています。

4. 将来の展望:
   因子写像（factor map）や総シミュレーション（total simulation）などの動的演算子を通じて、より単純なサブシフトに関連する問題が、元のサブシフトに関連する問題よりも常に「簡単」になるかどうかという一般的な命題の探求が今後の課題として提示されています。

総じて、この論文は多次元サブシフトの決定問題の複雑性を、パラメータの動的性質という視点から精密に分類し、計算理論と力学系の架け橋となる重要な知見を提供しています。