計算論的トポロジー

計算論的トポロジー（けいさんろんてきトポロジー、、、計算トポロジー等とも）は、（数学の幾何学における）トポロジーに関連する問題について、アルゴリズムや計算量等の計算機科学的側面を研究する分野で、純粋数学から計算幾何学やグラフィックス、ロボット工学、構造生物学や化学等、幅広い分野から生じる問題を対象とする。

分野毎の結果

3次元多様体論 3次元多様体に関する多くのアルゴリズムは正則曲面（normal surface）の理論を中心としたものである。

互いに同相でない3次元多様体を全て列挙する問題は、2020年7月現在未だ解決されていないが、3次元多様体の完全な分類はアルゴリズム的に可能であることが知られているS.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003。

三角形分割された3次元多様体が3次元球面に同相か否かを判定するアルゴリズムはに実装されているB.Burton. Introducing Regina, the 3-manifold topology software, Experimental Mathematics 13 (2004), 267-272.。その実行は四面体単体の数において指数関数時間的で、メモリ使用も指数的である。この問題はNPに含まれhttp://www.warwick.ac.uk/~masgar/Maths/np.pdf、更に一般化されたリーマン予想を仮定すればco-NPに含まれることも証明されている。

3次元多様体の連結成分毎の分解のアルゴリズムはに実装されている。アルゴリズムは3次元球面判定アルゴリズムに類似したもので、実行は指数関数時間である。

ザイフェイルト-ウェーバー多様体における不可縮曲面（incompressible surface）の存在を判定するアルゴリズムが知られている。

基本群が語の問題に対する解を有するような3次元多様体について双曲構造を検出するアルゴリズムが知られているJ.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1-26。

三角形分割された3次元多様体上の近似的双曲構造の計算アルゴリズムはSnapPeaに実装されている。

転換アルゴリズム

結び目のダイアグラム表示からcusped triangulationを生成するアルゴリズムが知られており、SnapPeaに実装されている。アルゴリズムは絡み目の補空間の基本群の表示を作るWirtingerのアルゴリズムと似たものである。このアルゴリズムはダイアグラムの交点数に対して凡そ線形の計算時間である。

3次元多様体の手術表示から、当該多様体の三角形分割表示に変換するアルゴリズムがSnapPeaに実装されている。

三角形分割された3次元多様体から三角形分割された4次元多様体を構成する手順が知られている。

曲面の写像類群の元をデーンツイストを生成元とする語の形で与えたときに、三角形分割された3次元多様体を生成するアルゴリズムが知られている（S. Schleimerによる）。生成される3次元多様体は、当該元をヘーガード分解の貼り合わせ写像と看做したときに作られるものである。

結び目理論

結び目が自明か否かを判定する問題はNPに属する.。

結び目の種数を決定する問題はPSPACEに属する。

結び目のアレキサンダー多項式を計算する多項式時間のアルゴリズムが存在する。

ホモトピー論球面のホモトピー群や（homotopy continuation）の数値的方法等が研究されている。

有限なPostnikov複体のホモトピー群を計算するアルゴリズムが知られているE H Brown's "Finite Computability of Postnikov Complexes" Annals of Mathematics (2) 65 (1957) pp 1-20。

ホモロジー論 CW複体のホモロジー群の計算は、アルゴリズム的には境界行列（boundary matrices）のスミス標準形（Smith normal form）への変形問題に帰着するが、複体が巨大な場合に効率的に計算するには種々の障碍がある。

位相的データ解析に関連して活溌に研究されている。

効率的な確率論的スミス標準形（Smith normal form）変形アルゴリズムが LinBoxライブラリに実装されている。

永続的ホモロジー（persistent homology）を計算するためのアルゴリズムがPerseus、TDAstats（R言語のパッケージ）等に実装されている。

脚注

参考文献

Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010,

計算論的トポロジー

Źródło i licencja