解く問題

数学において、結び目を解く問題とは、結び目の何らかの表現、例えば結び目図が与えられたときに、結び目のない部分をアルゴリズム的に認識する問題である。結び目を解くアルゴリズムにはいくつかの種類がある。未解決の主な課題は、問題が多項式時間アルゴリズムを許容するかどうか、つまり問題が複雑性クラスPに属するかどうかを判断することである。

計算複雑性を決定するための最初のステップは、問題がクラス P を含むより大きな複雑性クラスに属することを証明することで行われました。Hass、Lagarias、Pippenger (1999) は、与えられた結び目のSeifert 面を通常の曲面を使用して記述することにより、結び目を解く問題が複雑性クラスNPに属することを示しまし た。Hara、Tani、Yamamoto (2005) は、結び目を解くことはAM ∩ co-AMに属するという弱い結果を主張しました が、後にこの主張を撤回しました。^[1] 2011 年に、Greg Kuperberg は(一般化リーマン予想を仮定して) 結び目を解く問題はco-NPに属することを証明しました。^[2]また、2016 年にMarc Lackenby はco-NP のメンバーシップの無条件証明を提供しました。^[3]

2021年にラッケンビーは、準多項式時間で実行できると主張するアンクット認識アルゴリズムを発表しました。^[4] 2024年5月現在、その結果は査読済みの文献に掲載されていません。

結び目を解く問題は、ユークリッド空間における無向グラフの埋め込みがリンクレスであるかどうかをテストするのと同じ計算量である。^[5]

結び目を解く問題を解くいくつかのアルゴリズムは、ハーケンの正規面理論に基づいています。

• Haken のアルゴリズムは、正規表面の理論を使用して、結び目を境界とするディスクを見つけます。Haken はもともとこのアルゴリズムを使用して、結び目を解くことが決定可能であることを示しましたが、その複雑さを詳細に分析していませんでした。
• Hass、Lagarias、および Pippenger は、すべての正規表面の集合が多面体円錐の整数点によって表され、曲線の結び目のなさを証明する表面 (存在する場合) は常にこの円錐の端線のいずれかに見つかることを示した。したがって、頂点列挙法を使用して、すべての端線をリストし、それらのいずれかが結び目の境界ディスクに対応するかどうかをテストできます。Hass、Lagarias、および Pippenger はこの方法を使用して、結び目のなさが NP 内にあることを示しました。その後、Burton (2011a) などの研究者が分析を改良し、このアルゴリズムは有用である (ただし多項式時間ではない) こと、その複雑さが交差数の低次の単指数関数であることを示しました。
• Birman & Hirsch (1998) のアルゴリズムでは、通常の表面とは多少異なるタイプの構造である編組葉理構造を使用します。ただし、その動作を分析するために、通常の表面理論に戻ります。

その他のアプローチとしては、次のものがあります。

• 非結び目図を標準の非結び目図に変更するために必要なライデマイスター移動の数は、交差数の多項式以下です。^[6]したがって、ライデマイスター移動のすべてのシーケンスを総当たり検索すると、指数時間で非結び目性を検出できます。
• 同様に、同じ結び目の補集合の任意の 2 つの三角形分割は、交差回数の 2 倍指数以下の長さのPachner 移動のシーケンスによって接続できます。 ^[7]したがって、与えられた結び目の補集合から始めて、この長さの Pachner 移動のシーケンスをすべてテストし、それらのいずれかが補集合をソリッドトーラスの標準的な三角形分割に変換するかどうかを判断することで、結び目が非結び目かどうかを判断できます。この方法にかかる時間は 3 倍指数になりますが、実験的証拠は、この制限が非常に悲観的であり、必要な Pachner 移動がはるかに少ないことを示唆しています。^[8]
• 結び目のない円弧表現は、基本的な動きを使って、最小限の円弧表現に単調に単純化することができます。^[9]したがって、それほど複雑ではないすべての円弧表現を総当たりで探すと、結び目を解く問題に対する単一指数アルゴリズムが得られます。
• 結び目群の残差有限性（これはハーケン多様体の幾何化から得られる）は、群が非巡回有限群商を持つかどうかをチェックするアルゴリズムを与える。この考え方は、結び目を解く問題が co-NP にあるという Kuperberg の結果に使用されている。
• 結び目のフロアーホモロジーは結び目の種数を検出します。これは、結び目が非結び目である場合に限り 0 になります。結び目フロアーホモロジーの組み合わせバージョンを使用すると、これを計算できます (Manolescu、Ozsváth、Sarkar 2009)。
• Khovanov ホモロジーは、 KronheimerとMrowkaの結果に従って、結び目がない状態を検出します。^[10] Khovanov ホモロジーの計算量は、少なくともJones 多項式を計算する#P 困難問題と同じくらい高いですが、Bar-Natan (2007) のアルゴリズムとプログラムを使用して実際に計算できます。Bar-Natan は、彼のアルゴリズムの厳密な分析を提供していませんが、交差図のパス幅に対して指数関数的であると経験的に推定しており、パス幅はせいぜい交差数の平方根に比例します。

これらのアルゴリズムの複雑さを理解することは、活発に研究されている分野です。

• アルゴリズムトポロジー
• 解く数

• Bar - Natan, Dror (2007)、「高速コバノフホモロジー計算」、Journal of Knot Theory and Its Ramifications、16 (3): 243–255、arXiv : math.GT/0606318、doi:10.1142/S0218216507005294、MR  2320156 、S2CID  17036344。
• バーマン、ジョーン S. ; ヒルシュ、マイケル (1998)、「アンクノットを認識するための新しいアルゴリズム」、ジオメトリとトポロジー、2 : 178–220、arXiv : math/9801126、doi :10.2140/gt.1998.2.175、S2CID  17776505。
• バートン、ベンジャミン A. (2011a)、「正規曲面解空間の最大許容面と漸近境界」(PDF)、Journal of Combinatorial Theory、シリーズ A、118 (4): 1410–1435、arXiv : 1004.2605、doi :10.1016/j.jcta.2010.12.011、MR  2763065、S2CID  11461722。
• バートン、ベンジャミン (2011b)、「パクナーグラフと 3 球面三角形分割の簡略化」、Proc. 27th ACM Symposium on Computational Geometry、pp. 153–162、arXiv : 1011.4169、doi :10.1145/1998196.1998220、S2CID  382685。
• Dynnikov、Ivan (2006)、「リンクのアーク表示: 単調単純化」、Fundamenta Mathematicae、190 : 29–76、arXiv : math/0208153、doi :10.4064/fm190-0-3、S2CID  14137437。
• Haken、Wolfgang (1961)、「Theorie der Normalflächen」、Acta Mathematica、105 : 245–375、doi : 10.1007/BF02559591。
• 原 正夫、谷 誠一、山本 誠 (2005)、「アンノッティングは AM ∩ co-AM にある」、Proc. 16th ACM-SIAM Symposium on Discrete algorithms (SODA '05)、pp. 359–364。
• ハス、ジョエル;ラガリアス、ジェフリー C. ;ピッペンガー、ニコラス(1999)、「結び目とリンクの問題の計算複雑性」、Journal of the ACM、46 (2): 185–211、arXiv : math/9807016、doi :10.1145/301970.301971、MR  1693203、S2CID  125854。
• ハス、ジョエル;ラガリアス、ジェフリー C. (2001)、「結び目を解くために必要なライデマイスター移動の数」、アメリカ数学会誌、14 (2): 399–428、arXiv : math/9807012、doi :10.1090/S0894-0347-01-00358-7、MR  1815217、S2CID  15654705。
• 河原林 健一、ステファン クロイツァー、ボヤン モハル(2010)、「3 次元空間におけるリンクレスおよび平坦埋め込みとアンクノット問題」(PDF)、Proc. ACM Symposium on Computational Geometry (SoCG '10)、pp. 97–106、doi :10.1145/1810959.1810975、S2CID  12290801。
• クロンハイマー、ピーター。 Mrowka, Tomasz (2011)、「Khovanov ホモロジーは結び目検出器」、Publications Mathématiques de l'IHÉS、113 (1): 97–208、arXiv : 1005.4346、doi :10.1007/s10240-010-0030-y、S2CID  119586228
• Kuperberg, Greg (2014)、「結び目は NP にあり、GRH を法とする」、Advances in Mathematics、256 : 493–506、arXiv : 1112.0845、doi :10.1016/j.aim.2014.01.007、MR  3177300、S2CID  12634367。
• ラッケンビー、マーク(2015)、「ライデマイスター移動の多項式上限」、数学年報、第 2 シリーズ、182 (2): 491–564、arXiv : 1302.0180、doi :10.4007/annals.2015.182.2.3、MR  3418524、S2CID  119662237。
• ラッケンビー、マーク（2021）、「結び目性とサーストンノルムの効率的な証明」、Advances in Mathematics、387：107796、arXiv：1604.00290、doi：10.1016/j.aim.2021.107796、S2CID  119307517。
• マノレスク、チプリアン;オズヴァース、ピーター S. ;サーカー、スチャリット(2009)、「結び目フローアーホモロジーの組合せ的記述」、数学年報、第 2 シリーズ、169 (2): 633–660、arXiv : math/0607691、Bibcode :2006math......7691M、doi :10.4007/annals.2009.169.633、MR  2480614、S2CID  15427272。
• ミヤトヴィッチ、アレクサンダル (2005)、「結び目補集合の単純構造」、数学研究レター、12 (6): 843–856、arXiv : math/0306117、doi :10.4310/mrl.2005.v12.n6.a6、MR  2189244、S2CID  7726354