技術要約：観測者、対称性、および言語クラスの階層

問題提起

古典的な計算複雑性および形式言語理論は、伝統的に、計算能力（有限オートマトン、プッシュダウン・オートマトン、チューリングマシンなど）に基づく問題の分類を行い、入力は完全にアクセス可能な順序付けられた記号列であることを前提としている。本論文はこの視点を逆転させ、計算システムの限界は、計算能力からではなく、観測者の構造から生じる可能性があると仮定する。

対処される中心的な問題は、「完全な入力文字列ではなく、特定の射影または変換のみにアクセスできる場合、計算システムはどの言語を認識できるか？」という問いである。本論文は、観測者 $O: \Sigma^* \to S$（入力文字列を観測空間 $S$ へ写像する関数）の「盲目性」または「構造的制限」が、計算モデルとは独立して、認識可能な言語のクラスをどのように決定するかを調査する。

方法論

本論文は、観測者という概念を中心とした形式的な枠組みを導入する：

1. 観測者の定義: 観測者とは、入力文字列 $x$ を観測 $O(x)$ へと変換する関数である。計算システム $(M, O)$ は、$x$ の代わりに $O(x)$ を入力として受け取る。
2. O-飽和 (O-Saturation): 言語 $L$ が O-飽和 であるとは、 $L$ のメンバーシップが $O(x)$ のみに依存することを指す。形式的には、$x \sim_O y \implies (x \in L \iff y \in L)$ である。もしある言語が O-飽和でないならば、たとえどれほど強力な計算能力を持つ機械であっても、観測者 $O$ を備えた機械はその言語を判定できない。
3. 観測的順序 (Observational Order): 観測者に関する前順序 $\preceq$ が定義される。ここで、$O_1 \preceq O_2$ とは、$O_1$ が $O_2$ から導出可能である（すなわち $O_1 = f \circ O_2$）ことを意味する。これは言語クラスの階層 $\mathcal{L}(O)$ を誘導し、$O_1 \preceq O_2 \implies \mathcal{L}(O_1) \subseteq \mathcal{L}(O_2)$ となる。
4. 標準的観測者 (Canonical Observers): 階層を構築するために、以下の特定の観測者を定義する：
   • $O_\perp$: 自明な観測者（すべての文字列を定数に写像する）。
   • $O_{len}$: 長さ観測者（$|x|$ に写像する）。
   • $O_{par}$: パリティ観測者（2を法とするカウントに写像する）。
   • $O_{prof}$: プロファイル観測者（順序を無視した記号カウントのベクトルに写像する）。
   • $O_k$: 部分列観測者（長さ $\le k$ の部分列の集合に写像する）。
   • $O_\top$: 完全な観測者（恒等写像、$O(x) = x$）。

主な貢献と結果

1. オーダー盲目オートマトンと置換閉鎖言語

本論文は、文字列のシーケンスではなく、文字列のプロファイル（記号カウントのマルチセット）を処理する機械である、オーダー盲目オートマトンを特徴付ける。

• 定理 2.5: ある言語がオーダー盲目オートマトンによって認識可能であるための必要十分条件は、それが置換閉鎖的（記号の並べ替えに対して不変）であることである。
• この結果は、状態の有限性が主要な制約ではなく、むしろ観測者がクラスを決定することを示している。自明な観測者を持つチューリングマシンであっても、$\emptyset$ と $\Sigma^*$ しか認識できない。

2. 観測的階層

本論文は、標準的な観測者の観測能力に基づき、言語クラスの半順序を構築する。階層は特定の構造を示す：

• ダイヤモンド型のプロファイル副ラティス (Diamond-Shaped Profile Sub-lattice):
  • $O_\perp \prec O_{len} \prec O_{prof} \prec O_\top$ （長さの分岐）
  • $O_\perp \prec O_{par} \prec O_{prof} \prec O_\top$ （パリティの分岐）
  • $O_{len}$ と $O_{par}$ は比較不能である。
• 無限の部分列分岐:
  • $O_\perp \prec O_1 \prec O_2 \prec \dots \prec O_\top$。
  • この分岐は、Simon の piecewise testable 言語の階層に対応する。
• 直交性: プロファイル副ラティス（計数情報）と部分列分岐（部分順序情報）は**直交（比較不能）**である。$O_{prof}$ は任意の $O_k$ と比較不能である。

3. チョムスキー階層との直交性

本論文は、観測的階層がチョムスキー階層（正規、文脈自由など）に対して厳密に**直交（比較不能）**であることを証明する。

• 正規であるが O-飽和ではない言語が存在する（例：$0^*1^*$ は $O_{prof}$-飽和ではない）。
• O-飽和であるが正規ではない言語が存在する（例：$\{x \mid |x|_0 = |x|_1\}$ は $O_{prof}$-飽和であるが正規ではない）。
• これにより、「構造的盲目性」と「計算複雑性」が独立した軸であることが確立される。

4. Simon の階層との関連

本論文は、piecewise testable 言語に関する Simon の定理を再定式化する。

• 観測者の族 $\{O_k\}$ は、Simon の階層における同値関係に正確に対応する。
• 正規言語が piecewise testable であるための必要十分条件は、ある有限な $O_k$ によって決定可能であることである。
• プロファイルクラス $\mathcal{L}(O_{prof})$ と piecewise testable 言語の和集合 $\bigcup_k \mathcal{L}(O_k)$ は比較不能である。

5. 観測者パラメータ化された複雑性クラス (PO および NPO)

この枠組みは、複雑さを入力サイズ $|x|$ ではなく、観測のサイズ $|enc(O(x))|$に対して測定する、クラス$PO$および$NPO$ へと拡張される。

• 構造的崩壊 (Structural Collapse): 本論文は $PO_{prof} = NPO_{prof}$ を証明する。
  • 意義: これは $P$ 対 $NP$の解決ではない。むしろ、これは**構造的崩壊**である。なぜなら、観測者$O_{prof}$ はすべての組合せ的構造（順序）を破棄するからである。順序がなければ、非決定性は決定論に対して優位性を持たない。
  • 厳密な包含関係: $PO_{prof} \subsetneq P$ である。クラス $PO_{prof}$ は、プロファイルサイズに対して多項式時間で計算可能な $O_{prof}$-飽和言語のみを含む。$0^*1^*$ は $P$ に属するが $O_{prof}$-飽和ではないため、包含関係は厳密である。
• 困難さと盲目の独立性: 本論文は、計算の困難さと観測の決定可能性が独立していることを示す。$P$ に属するが $O_{prof}$-飽和ではない言語が存在し、一方で RE（帰納的に列挙可能）クラスの外にあるが $O_{prof}$-飽和である言語（例：記号カウントに関する停止問題によって定義される言語）も存在する。

意義と主張

本論文は、形式言語および計算問題を分類するための、新しい独立した軸を導入することを主張している。その主な意義は以下の通りである：

1. 機械の能力と観測者構造の分離: 「弱い」観測者がチューリングマシンにとっての問題を解決不可能にできる一方で、より弱い機械（DFAなど）がより強い観測者を用いて問題を解決できることを確立した。
2. 困難さと盲目の区別: 計算の困難さ（アルゴリズムの複雑さに起因する難しさ）と構造的盲目性（情報の欠落により入力を区別できないこと）を形式的に分離した。$PO_{prof} = NPO_{prof}$ という崩壊は、これらが異なる現象であることの証拠として提示されている。この崩壊は、非決定性が本質的に弱いからではなく、観測者が問題を困難にするための構造そのものを取り除いてしまうために起こる。
3. 物理的解釈: 本枠組みは、統計力学への形式的なアナロジーを提供する。そこでは、マクロな観測者（温度や密度などの集約量のみを見る観測者）は、互いに置換の関係にあるミクロな履歴を区別できない。これは、「熱力学的不可逆性」を観測的特性として捉えるための数学的基礎を提供する。

本論文は、観測的階層が、情報が本質的に制限されている、あるいは集約されているシステムを分析するための厳密な枠組みを提供すると結論付けており、今後の研究において、確率的観測者、観測者の圏論的合成、および観測的複雑性と情報保存の定量的関係を探求することを提案している。