Computational complexity

計算論的観点：数学的構造とアルゴリズムの融合

従来の数学が「解の存在」を問うのに対し、計算論的観点は「その構造をいかに効率的に構成し、判定できるか」を問います。

1. 最適化（Optimization）

• 交互最小化（Alternate Minimization）: 多変数の関数に対し、一部の変数を固定して最適化を繰り返す手法。シンクホーン・アルゴリズム（Sinkhorn’s algorithm）などのスケーリング問題で中心的な役割を果たします。
• 測地的凸性（Geodesic Convexity）: 非ユークリッド空間（リーマン多様体など）における凸性を利用した勾配法。非可換な構造を持つ問題の効率的な解決を可能にします。
• Brascamp-Lieb 多面体とエントロピー: 解析学における不等式の定数を、凸最適化やエントロピーの最大化問題として捉え直します。

2. 不変式論（Invariant Theory）

群作用の下で変化しない性質を研究する不変式論は、アルゴリズム問題です。

• 軌道閉包の共通部分（Orbit Closure Intersection）: 2つのデータ（行列やテンソル）が、群の作用（回転や引き伸ばし）を通じて本質的に「同じ」ものかどうかを判定します。
• Nullcone問題: 与えられた点が、群作用によって原点にいくらでも近づけられるかを判定する問題。これは、計算量理論における「ゼロ判定」に直結します。
• グレブナー基底を避けるアルゴリズム: 従来の計算機代数では計算コストが高すぎるため、不変式の次数境界（Degree bounds）を利用した、より効率的な多項式時間のアルゴリズムが模索されています。

3. 計算複雑性理論（Computational Complexity）

代数的な回路や行列の性質から、計算の限界を探ります。

• 多項式恒等式判定 (PIT): 与えられた代数回路が恒等的にゼロかどうかを判定する問題。P
• 幾何学的複雑性理論 (GCT): 代数幾何学と表現論を用いて、P と NP（あるいは行列乗算の計算量）の間に「幾何学的な障害」があることを証明しようとする壮大な試みです。
• テンソルの階数 (Tensor Rank): 行列のランクの概念を多次元（テンソル）に拡張したもの。これが計算できれば、超高速な行列乗算アルゴリズムが見つかります。

4. 量子情報理論（Quantum Information Theory）

量子状態の「計算資源」としての性質を定義します。

• Completely Positive Operators: 量子チャネルの数学的表現。
• 量子蒸留 (Quantum Distillation): ノイズの多い量子状態から、純粋なもつれ（エンタングルメント）を抽出するプロセス。これを効率的な「スケーリングアルゴリズム」として記述します。
• エンタングルメント多面体: 複数の量子ビット間の相関関係を、幾何学的な多面体（Moment polytopes）の影として理解します。