Algebraic Circuits Over Sum and Shift and Existential Presburger Arithmetic with Divisibility

技術要約：和とシフトに関する代数回路、および除法を含む存在量化述語付きプレスバーガー算術

問題設定
本論文は、**除法を含む存在量化述дя付きプレスバーガー算術（EPAD）**の計算複雑性を調査している。標準的な存在量化プレスバーガー算術はNP完全であることが知られているが、除法述語（$f(x) \mid g(x)$）の追加は、その景観を大きく変える。EPADの充足可能性問題は長らくNP困難であるとされてきたが、それがNPに含まれるのではないかという「フォークロア」的な予想が存在していた。本論文は、より強い下界を確立することで、この予想に異を唱えるものである。

手法
著者らは、制限された算術回路モデル上で定義された特定の計数問題から、EPADの充足可能性への帰着を用いる。その手法は、主に以下の3つの段階で進行する：

1. 和－シフト回路と係数： 著者らは、和－シフト回路（sum-shift circuits）と呼ばれる制限された算術回路モデルを定義する。これらの回路は、加算ゲートと「シフト」ゲート（単項式 $x^a$ による乗算）のみを用いて多項式を操作するものであり、一般的な乗算ゲートは持たない。簡潔さ（succinctness）の唯一の源泉は、部分回路の共有である。著者らは、Coeff問題（そのような回路によって計算される多項式の特定の単項式 $x^t$ の係数を求める問題）を定義する。そして、閾値版であるCoeff-LT（係数が与えられた $K$ 未満であるかどうかを判定する問題）が PP完全 であることを証明する。これは、和－シフト回路が部分和問題の母関数 $\prod (1 + x^{a_i})$ を簡潔に表現できるという事実に依拠している。

2. 除法ガジェットによるEPADへの帰着： 著者らは、Coeff-LT を EPAD の充足可能性へと帰着させる。この帰着では、回路を大きな基数 $B = 2^b$ で評価する。このエンコーディングにおいて：

   • 加算ゲートは線形等式となる。
   • シフトゲート（$x^a$）は、$2^a$ 倍による乗算を強制する多項式サイズの線形除法制約のシステムによってシミュレートされる。
   • 決定的なのは、変数間の特定の乗法的関係（例えば $v = (2^{2^j} + 1)u$）を強制するスケーリング・ガジェットの構築である。これらのガジェットは、**マージ・アブソーブティブ（merge-absorptive）**特性、すなわち EPAD の特定の構造的断片を利用している。

3. 正規化と係数の膨張に関する分析： 著者らは、構築されたシステムに対する正規化手順（具体的には Kernel Normal Form、または KNF）の挙動を分析する。彼らは、入力システムが小さい（多項式サイズ）一方で、強制された乗法的関係（例：$v = F_j u$ ただし $F_j = 2^{2^j} + 1$）を単一の原始的な方程式として記録するいかなる正規化ステップも、指数的なビットサイズ（$\Theta(2^j)$）の係数を導入しなければならないことを示している。

主要な貢献

• EPADのPP困難性： 主要な結果は、EPADの充足可能性が PP困難 であることである。これは、$\text{NP} = \text{PP}$ でない限り、EPADがNPに含まれる可能性を排除するものである。
• マージ・アブソーブティブ断片： 著者らは、EPADの多項式時間で認識可能な断片であるマージ・アブソーブティブを定義する。この断片のシステムでは、「有限商簡略化（finite-quotient simplification）」が可能であり、除法原子が線形方程式の有限な選言に置き換えられる。彼らは、完全に簡略化可能なこの断片に制限しても、EPADの充足可能性が依然としてPP困難であることを証明する。
• 和－シフト回路の複雑性： 本論文は、和－シフト回路の係数問題が #P完全であり、その閾値版がPP完全であることを確立している。これは、困難性の証明のための新しい制限された代数モデルを提供する。
• 正規化の障害： 著者らは、正規化戦略の限界を明確にしている。EPADをNPに配置することに対する障害は、以下の二重の構造を持つことを示している：
  1. 計数による下界（PP困難性）は、たとえ正規化が多項式個の分岐を生み出したとしても、結果として得られる問題が依然としてPP困難であることを意味する。
  2. 正規化された方程式における係数自体が指数的なサイズに膨張するため、正規化された形式のコンパクトな表現が不可能になる。

結果

• 定理 20： EPAD-SAT は、多項式時間多対一還元（polynomial-time many-one reductions）の下でPP困難である。この下界は、宣言された厳密な順序制約を持つ、マージ・アブソーブティブな正の同次線形除法システムへの充足可能性に対しても成立する。
• 定理 30： スケーリング・ガジェットの族 $\Gamma_j$ に対して、強制された終点関係 $v = (2^{2^j} + 1)u$ を原始的なアフィン方程式を通じて露出させるいかなる修復ステップ（Lipshitz正規化における置換ベースのステップ、またはKNFフレームワークのいずれにおいても）も、$\Theta(2^j)$ のビットサイズを持つ係数を生み出さなければならない。
• 文字列制約に関する系： 著者らは、彼らの下界が、単語方程式（word equations）と長さ制約の正のブール結合の充足可能性問題についてもPP困難であることを意味すると指摘しており、これは Day と Konefal による先行研究を拡張するものである。

意義と主張
本論文は、EPADの充足可能性に関する長年のNP困難という下界に対する、初の改善を提供すると主張している。彼らは、EPADがNPに含まれるというフォークロア的な予想を明確に否定している。

その意義は、和－シフト回路が除法制約を通じて二重指数的な乗算器を生成できるという、特定の算術的メカニズムを特定した点にある。著者らは、困難さは単に巧妙なアルゴリズムの欠如によるものではなく、問題の構造に固有のものであると論じている：

1. 計算理論的障壁： 問題は本質的にNPよりも難しく（$\text{NP} = \text{PP}$ でない限り）、
2. 表現の障壁： 正規化によってシステムを簡略化しようとしても、解空間を表現するために必要な係数が膨張するため、コンパクトな表現が不可能になる。

本論文は、計数の下界、簡略化可能な断片が依然として困難であること、そして正規化における係数の膨張のすべてが、同一の根底にある算術的メカニズムに由来することを結論づけている。これはEPADを解くための新しいアルゴリズムを提案するものではなく、むしろそのようなアプローチの理論的限界を定めるものである。