単体複素数認識問題

単体複体認識問題は、代数トポロジーにおける計算問題である。与えられた単体複体が、別の固定された単体複体と同相であるかどうかを判定することが問題である。この問題は、次元が5以上の複体では判定不能である。^{[ 1 ] [ 2 ]： 9-11}

抽象単体複体（ASC）とは、部分集合を取る操作に関して閉じている集合の族（族内の集合の部分集合もまた族内の集合である）のことです。すべての抽象単体複体は、ユークリッド空間において幾何学的単体複体（GSC）として一意に幾何学的に実現されます。ASC内のk個の要素を持つ各集合は、 GSC内の( k -1)次元単体に写像されます。したがって、ASCは幾何学的対象の有限表現を提供します。ASCが与えられた場合、それが表すGSCのトポロジーに関していくつかの質問をすることができます。

同相問題とは、滑らかな多様体を表す2つの有限単体複体が与えられたとき、それらが同相であるかどうかを判定することです。

• 複体の次元が最大でも３であれば、この問題は決定可能である。これは幾何化予想の証明から導かれる。
• d ≥ 4 の場合、d次元単体複体の同相問題は決定不能である。^{[ 3 ]}

「同相」を「区分的線形同相」に置き換えた場合も同様である。

認識問題は同相問題の部分問題であり、固定パラメータとして1つの単体複体が与えられます。入力として別の単体複体が与えられた場合、それが与えられた固定複体と同相であるかどうかを判定することが問題となります。

• 認識問題は3次元球体に対しては決定可能である。$\displaystyle S^{3}}$^{[ 4 ]}つまり、任意の単体複体が4次元球の境界と同相であるかどうかを判定できるアルゴリズムが存在する。
• d次元球面における認識問題は決定不能である。${\displaystyle S^{d}}$任意の d ≥ 5 に対して。証明は群の語問題からの還元による。これから、 d ≥ 5 の任意の固定されたコンパクトなd次元多様体に対して認識問題が決定不能であることが証明できる。
• 2014年現在、4次元球面における認識問題が決定可能かどうかは未解決である。$\displaystyle S^{4}}$[ ^{2 ]： 11​}

多様体問題とは、有限単体複体が与えられたとき、それが多様体と同相であるかどうかという問題である。この問題は決定不能であり、証明は群の語問題からの還元によって行われる。^{[ 2 ]： 11}