技術的概要：ルカシェヴィッチ論理における充足可能性とその無界相対

問題定義

本論文は、無界ルカシェヴィッチ論理（$L_u$）の存在論理（充足可能性問題）の計算複雑性を取り扱っている。$L_u$ は、無限値ルカシェヴィッチ論理（$L$）の特性とアーベル論理の特性を組み合わせた部分構造論理である。その意図された意味論は、実数上の点付きアーベル全順序加法群であり、$\mathbb{R}_{-1}$ と表記される。ここで、定義域は $\mathbb{R}$ であり、区別された定数 $-1$ が偽を表す。

標準ルカシェヴィッチ論理（$L$）の複雑性はよく確立されている。具体的には、標準 MV-代数 $[0, 1]_L$ における項の充足可能性はNP 完全である（Mundici [35]）。しかし、$L_u$（およびその基礎となる代数 $\mathbb{R}_{-1}$）の存在論理の複雑性は、標準ルカシェヴィッチ論理への還元という文脈において明示的に決定されていなかった。著者らは、$\mathbb{R}_{-1}$ の存在論理と $[0, 1]_L$ の存在論理との間の多項式時間還元を確立することにより、$L_u$ に対する複雑性の見積もりを提供することを目的としている。

手法

本論文は、代数的還元と有界モデル分析を含む二重の手法論的アプローチを採用している。

1. 充足割り当ての有界性

著者らはまず、$\mathbb{R}_{-1}$ において存在文が成り立つ場合、それが特定の多項式有界区間内の充足割り当てを持つことを確立する。

• 補題 3.2（有界割り当て）: 点付き $\ell$-群の言語（$L_{pAb}$）における任意の開式 $\Phi$ について、$\mathbb{R}_{-1} \models \exists \bar{x} \Phi$ ならば、$\Phi(\bar{a})$ が成り立つような有理数割り当て $\bar{a}$ が存在し、$\bar{a}$ の値の二進表現サイズは $\Phi$ のサイズに対して多項式である。
• この結果は、充足可能性問題を線形不等式系に還元し、クラメルの法則から導出された境界（補題 3.1）を適用することに基づいており、解が $M$ が式サイズと多項式的に関連する区間 $[-2^M, 2^M]$ 内に存在することを保証する。

2. 線形写像による多項式時間還元

手法論の中核は、$\mathbb{R}_{-1}$ の存在論理から標準 MV-代数 $[0, 1]_L$ の存在論理への多項式時間還元である。

• 写像の構成: 著者らは、$L_{Ab}$（アーベル $\ell$-群）の項から $L_{MV}[1/2]$（定数 $1/2$ を持つ MV-代数）の項への写像 $\tau$ を定義する。この写像は、$\mathbb{R}$ 内の有界区間 $[-2^M, 2^M]$ を $[0, 1]$ の部分区間に写す線形変換 $r_{M,k}(a) = \frac{a}{2^{M+k+1}} + \frac{1}{2}$ を利用する。
• 項の翻訳: この線形写像の下で、項の深さが有界である限り、翻訳 $\tau$ は項の意味論的構造（加法、否定、束演算）を保存する。
• 複雑性の処理: 項サイズの指数関数的な増大（ネストされた加法の単純な翻訳で発生する）を防ぐため、著者らはツェイトイン変換を採用する。これは部分項に対して新しい変数を導入し、項の深さを最大 1 に抑えた多項式サイズの同値充足可能式へ複雑な式を変換する。
• 定数の符号化: $\mathbb{R}_{-1}$ における定数 $-1$は、特定の方程式（例：$z_1 = \neg z_1$, $z_{i+1} \oplus z_{i+1} = z_i$）によって制約された補助変数（$z_i, q, r$）を用いて MV-代数内で符号化される。これらは標準意味論において特定の有理数値（$1/2$ のべき乗）を強制する。

3. ルカシェヴィッチ論理の自己還元

本論文は、$[0, 1]_L$ から $\mathbb{R}_{-1}$ への還元（先行研究 [12] で確立されたもの）と、$\mathbb{R}_{-1}$ から $[0, 1]_L$ への新しい還元との合成についても調査する。

• 著者らは、$L_{MV}$ の項を直接 $L_{MV}[1/2]$ の項に写す合成翻訳 $\sigma_q$ を定義する。
• 彼らは、この合成が多項式サイズの翻訳をもたらすことを証明し、実質的に $[0, 1]_L$ の存在論理に対する非自明な自己還元を提供する。

主要な結果

1. $L_u$ 存在論理の NP 完全性: $\mathbb{R}_{-1}$ の存在論理（したがって無界ルカシェヴィッチ論理の定理の集合と有限帰結関係）はNP 完全である。

   • 上限: 充足割り当てが多項式有界区間内に見つかるため（補題 3.2）、かつ $[0, 1]_L$ への還元（既知の NP 完全）が多項式時間であるため（定理 4.6）、本問題は NP に属する。
   • 下限: 困難性は、$[0, 1]_L$ における項の充足可能性の既知の NP 完全性（Mundici [35]）と、$[0, 1]_L$ から $\mathbb{R}_{-1}$ への多項式時間還元の存在（[12] より）に由来する。

2. 普遍部分式の coNP 完全性: したがって、$\mathbb{R}_{-1}$ の普遍論理、方程式論理、および準方程式論理はcoNP 完全である。

3. $[0, 1]_L$ の自己翻訳: 本論文は、標準 MV-代数 $[0, 1]_L$ の存在論理をそれ自身へ多項式時間で還元することを示す（定理 5.6）。これは、$\mathbb{R}_{-1}$ への還元と $[0, 1]_L$ への還元を合成することによって達成される。

意義と主張

著者らは、この研究の主な貢献は複雑性の結果そのものではなく、還元手法であると主張している。関連構造の既知の複雑性を考慮すれば、この結果は予期されたものかもしれない。

• 新たな接続: この還元は、無界ルカシェヴィッチ論理（$L_u$）と標準ルカシェヴィッチ論理（$L$）との間の新しい明示的な接続を確立する。それは、0 の十分に大きな近傍を区間 $[0, 1]$ へ写す線形写像を介して、無界論理の充足可能性問題を標準論理へ効果的に翻訳できることを示している。
• 明示的還元: 実閉体の $L_{\Pi 1/2}$ への還元（Marchioni と Montagna [31] によるもの）のように、抽象的な存在や異なる論理枠組みに依存する以前の手法とは異なり、本論文は言語の部分構造へもよくスケーリングする明示的な多項式時間還元を提供する。
• 理論的洞察: この結果は、標準 MV-代数の存在論理をそれ自身へ翻訳することを伴う。著者らは、これが他の論理的還元との比較を誘うことに言及しつつ、自らの手法は乗法的関数記号を必要とせず、加法構造と線形写像に依存していることを強調している。

本論文は、$L_u$ における充足可能性の問題が決定可能であり、無限値性にもかかわらず、その古典的命題的対応物（NP 完全）と同じ複雑性クラスに位置することを結論付けている。