計算トポロジー

3次元多様体に関するアルゴリズムの大きなファミリーは、正規曲面理論を中心に展開されており、これは3次元多様体理論における問題を整数線形計画問題に変換するためのいくつかの手法を包括する用語である。

• ルビンシュタインとトンプソンの 3 球面認識アルゴリズム。これは、三角形分割された3 多様体を入力として受け取り、その多様体が3 球面と同相であるかどうかを判定するアルゴリズムです。このアルゴリズムは、初期 3 多様体の四面体単体の数に対して指数関数的な実行時間と指数関数的なメモリ プロファイルを持ちます。ソール シュライマーは、この問題が複雑性クラスNPに属することを示しました。^{[ 4 ]}さらに、ラファエル ツェントナーは、一般化リーマン予想が成り立つ場合 、この問題が複雑性クラス coNP に属することを示しました。 ^{[ 5 ]}彼は、インスタントン ゲージ理論、3 多様体の幾何化定理、および結び目検出の複雑性に関するグレッグ クーパーバーグのその後の研究^{[ 6 ]を使用しています。}
• 3次元多様体のコネクトサム分解もReginaに実装されており、実行時間は指数関数的に長く、3次元球面認識アルゴリズムと同様のアルゴリズムに基づいています。
• ^{ザイフェルト・ウェーバー3次元多様体には非圧縮性表面が存在しないことを判定するアルゴリズムは、バートン、ルビンシュタイン、ティルマン[ 7 ]}によって実装され、正規表面理論に基づいている。
• マニングアルゴリズムは、基本群が単語問題の解を持つ3次元多様体上の双曲構造を見つけるアルゴリズムである。^{[ 8 ]}

現在、JSJ分解はコンピュータソフトウェアでアルゴリズム的に実装されていません。圧縮ボディ分解も同様です。三角形分割された3次元多様体上の近似双曲構造を計算することに大きな成功を収めているSnapPeaなど、非常に人気があり成功しているヒューリスティックがいくつかあります。3次元多様体の完全な分類はアルゴリズム的に実行できることが知られています^{[ 9 ]。}実際、三角形分割（単体複体）によって与えられる2つの閉じた向き付けられた3次元多様体が同等（同相）であるかどうかを判定することは、基本的な再帰であることが知られています。^{[ 10 ]}これは、3次元球面認識の結果を一般化したものです。

結び目が自明であるかどうかを判定することは、複雑性クラスNP ^{[ 12 ]}およびco-NP ^{[ 13 ]}に属することが知られています。3次元多様体における結び目の種数を決定する問題はNP 完全です。^{[ 14 ]}ただし、NP はR ³または S ³における結び目の種数を決定する複雑性の上限として残っていますが、2006 年時点では、これらの特定の 3 次元多様体における結び目の種数を決定するアルゴリズムの問​​題がまだNP 困難であるかどうかは不明でした。^{[ 14 ]}

• 球面のホモトピー群の計算方法。
• 多項式方程式系を解くための計算手法。
• ブラウンは有限ポストニコフ複体である空間のホモトピー群を計算するアルゴリズムを持っているが、^{[ 15 ]}広く実装可能とは考えられていない。

セル複合体の相同群の計算は、境界行列をスミス正規形に変換することに帰着します。これはアルゴリズム的には完全に解決された問題ですが、大規模な複合体に対して効率的な計算を行うには、さまざまな技術的な障害があります。主な障害は 2 つあります。まず、基本的なスミス正規形アルゴリズムは、行と列の操作を使用するため、対象となる行列のサイズに対して 3 乗の計算量となり、大規模なセル複合体には適していません。次に、スミス正規形アルゴリズムを適用した結果得られる中間行列は、疎行列から始めて疎行列で終了した場合でも、埋め尽くされてしまいます。

• LinBoxライブラリに含まれるような、効率的かつ確率的なスミス標準形アルゴリズム。
• Perseusソフトウェアパッケージのように、ホモロジー計算の前処理のための単純なホモトピック還元。
• TDAstats Rパッケージのように、フィルタリングされた複合体の永続的な相同性を計算するアルゴリズム。 ^{[ 16 ]}
• トポロジカルデータ解析（TDA）などの一部のアプリケーションでは、（コ）ホモロジークラスの代表が可能な限り「小さい」ことが有用です。これは（コ）ホモロジー局所化の問題として知られています。三角形分割された多様体では、ホモロジークラスを表すチェーンが与えられた場合、最小サポートの相同チェーンを近似することは一般にNP困難です。^{[ 17 ]}しかし、三角形分割された2-多様体上の1-コホモロジー局所化を近似するという特定の設定は、ユニークゲーム予想と同等の困難さを持つ既知の3つの問題の1つです。^{[ 18 ]}