Topological Complexity

Lusternik-Schnierelmann category に近い不変量として Farber が topological complexity というものを [Far03] で定義した。

この topological complexity という用語は, algorithm の複雑性の研究に代数的トポロジーの道具を用いた Smale の仕事 [Sma87] に登場する。そこでは, 代数方程式の根を求める algorithm の複雑性を考えるために Schwarz genus が用いられている。 Farber 自身, [Far03] の Introduction の最後で, Smale の仕事で Schwarz genus が使われていることを述べているので, topological complexity という名前は Smale の論文から取ったものだろう。

Farber の motivation は motion planning, つまり二点 \(x_0, x_1 \in X\) に対し, \(x_0\) を始点とし \(x_1\) を終点とする道を \(x_{0}\) と \(x_{1}\) に関し, 連続的に選ぶ方法があるか, という問題である。 Farberは, motion planning について topological robotics というタイトルの論文 [FTY03; FY04] を書いている。

• motion planning

つまり, 道の始点と終点を対応させる写像 \[ \pi : \mathrm {Map}(I,X) \longrightarrow X\times X \] の連続な cross section が存在するか, という問題である。\(X\times X\) 全体では存在しないかもしれないが, \(X\times X\) を適当な開集合に分割すれば, その小さな開集合上では存在するかもしれない。その開集合の最小数が \(X\) の topological complexity \(\mathrm {TC}(X)\) である。

• 位相空間 \(X\) に対し \(\mathrm {TC}(X)\) の定義

まず知っておくべきことは, \(\pi \) の global なmotion planning が存在するのは可縮な空間の場合のみであることである。

• motion planning が存在するための必要十分条件は, \(X\) が可縮であることである。

このことから, topological complexity が Lusternik-Schnierelmann category と関係が深いことが分かる。 ただ, その関係はそれほど単純なものではない。 Dan Cohen と Suciu の計算 [CS06] から, 次のことが分かる。

• \(\mathrm {TC}(X)-\mathrm {cat}(X)\) は, いくらでも大きくなり得る。

また \(\pi \) は fibration だから Schwarz genus とも関係がある。

基本的な性質は以下の通りである。全て Farber の論文に書いてある。

• \(\mathrm {TC}(X)\) はホモトピー不変量である。
• \(X\) が path-connected paracompact locally contractible space ならば \[ \mathrm {TC}(X) \le 2\dim X -1 \]
• \(X\) が path-connected paracompact space ならば \[ \mathrm {cat}(X) \le \mathrm {TC}(X) \le 2\mathrm {cat}(X)-1 \]
• カップ積 \[ H^*(X;k)\otimes H^*(X;k) \longrightarrow H^*(X;k) \] の kernel を \(I\) とおくとき, \(\mathrm {TC}(X)\) は \(I\) の元の列で, 積が \(0\) にならないものの長さで最大なもの以下である。
• \(X\) の topological complexity は \(\pi \) の Schwarz genus と一致する。
• \(X\) と \(Y\) が path-connected な 距離空間ならば \[ \mathrm {TC}(X\times Y) \le \mathrm {TC}(X) + \mathrm {TC}(Y) -1 \]

「小さな」 基本群を持つ空間の topological complexity の upper bound については, [CF10] で調べられている。

具体的な空間に対して決定されている場合を, 次のページにまとめた。

• topological complexity が知られている空間

実射影空間の immersion の問題との間には密接な関係がある。Farber と Tabachnikov と Yuzvinsky の [FTY03] である。その後, Gonzalez や Grant ら, 他の人によっても調べられている。Gonzalez と Landweber の [GL09] の Introduction をみるとよい。

変種も, 新しいものがどんどん導入されている。 まず symmetric version と higher version がある。

• symmetric topological complexity (Farber と Grant [FG07])
• symmetrized topological complexity ([Bas+14])
• higher topological complexity (Rudyak [Rud10])
• higher topological complexity for fibrations (Is と Karaca [İK22])
• higher symmetric topological complexity (Rudyak [Rud10])
• higher simplicial complexity (Borat [Bor20] と Paul [Pau19])
• higher combinatorial complexity (Paul [Pau19])
• higher symmetric simplicial complexity (Paul と Sen の [PS23])
• higher symmetric combinatorial complexity (Paul と Sen の [PS23])

他にも色々あって, とりあえず目にしたものを挙げると次のようになるが, 多分抜けているものもあると思う。

• Q-topological complexity (Fernández Suárez と Vandembroucq [FV18])
• simplicial complexity (González [Gon18])
• discrete topological complexity (Fernández-Ternero と Macías-Virgós と Minuz と Vilches の [Fer+18])
• combinatorial topological complexity for finite spaces (Tanaka [Tan18])
• geodesic complexity (Davis と Recio-Mitter [DR21])
• directed topological complexity (Goubault [Gou])
• homotopic distance (Macias-Virgos と Mosquera-Lois [MM22])
• abstract topological complexity (Diaz, Garcia Calcines, Garcia Diaz, Murillo, Remodios Gomez [Día+12])
• parametrized topological complexity (Cohen, Farber, Weinberger [CFW21])
• relative topological complexity (Short [Sho18])

Equivariant 版については Colman と Grant [CG12] により最初に定義されたが, その後 Lubawski と Marzantowicz の [LM], Dranishnikov の [Dra15], Błaszczyk と Kaluba の [BK18] といった, 異なるアプローチが提案されている。 それらの比較, そして nonequivariant 版との比較については, Ángel と Colman の [ÁC18] を見るとよい。

• 群の作用を持つ空間の topological complexity

Small categoryでの類似は, Macías-Virgós と Mosquera-Lois [MM20] により導入されている。彼等の homotopic distance の概念 [MM22] の類似を functor に対し定義し, それを用いて定義している。 更に, 彼等は Carcacía-Campos との共著 [CMM] で, higher homotopic distance を導入し, それを用いて higher topological complexity を導入している。

• small category の topological complexity
• small category の higher topological complexity

References

[ÁC18]

Andrés Ángel and Hellen Colman. “Equivariant topological complexities”. In: Topological complexity and related topics. Vol. 702. Contemp. Math. Amer. Math. Soc., [Providence], RI, [2018] ©2018, pp. 1–15. arXiv: 1709.00642. url: https://doi.org/10.1090/conm/702/14103.

[Bas+14]

Ibai Basabe, Jesús González, Yuli B. Rudyak, and Dai Tamaki. “Higher topological complexity and its symmetrization”. In: Algebr. Geom. Topol. 14.4 (2014), pp. 2103–2124. arXiv: 1009.1851. url: http://dx.doi.org/10.2140/agt.2014.14.2103.

[BK18]

Zbigniew Błaszczyk and Marek Kaluba. “Effective topological complexity of spaces with symmetries”. In: Publ. Mat. 62.1 (2018), pp. 55–74. arXiv: 1510.08724. url: https://doi.org/10.5565/PUBLMAT6211803.

[Bor20]

Ayse Borat. “Higher dimensional simplicial complexity”. In: New York J. Math. 26 (2020), pp. 1130–1144. url: https://nyjm.albany.edu/j/2020/26-46.html.

[CF10]

Armindo Costa and Michael Farber. “Motion planning in spaces with small fundamental groups”. In: Commun. Contemp. Math. 12.1 (2010), pp. 107–119. arXiv: 0806.4113. url: https://doi.org/10.1142/S0219199710003750.

[CFW21]

Daniel C. Cohen, Michael Farber, and Shmuel Weinberger. “Topology of parametrized motion planning algorithms”. In: SIAM J. Appl. Algebra Geom. 5.2 (2021), pp. 229–249. arXiv: 2009.06023. url: https://doi.org/10.1137/20M1358505.

[CG12]

Hellen Colman and Mark Grant. “Equivariant topological complexity”. In: Algebr. Geom. Topol. 12.4 (2012), pp. 2299–2316. arXiv: 1205.0166. url: https://doi.org/10.2140/agt.2012.12.2299.

[CMM]

I. Carcacía-Campos, E. Macías-Virgós, and D. Mosquera-Lois. Homotopy invariants in small categories. arXiv: 2206.00651.

[CS06]

Daniel C. Cohen and Alexander I. Suciu. “Boundary manifolds of projective hypersurfaces”. In: Adv. Math. 206.2 (2006), pp. 538–566. arXiv: math/0502506. url: http://dx.doi.org/10.1016/j.aim.2005.10.003.

[Día+12]

F. J. Díaz, J. M. Garcia Calcines, P. R. García Diaz, A. Murillo Mas, and J. Remedios Gómez. “Abstract sectional category”. In: Bull. Belg. Math. Soc. Simon Stevin 19.3 (2012), pp. 485–505. arXiv: 1106.5010. url: http://projecteuclid.org/euclid.bbms/1347642378.

[DR21]

Donald M. Davis and David Recio-Mitter. “The geodesic complexity of \(n\)-dimensional Klein bottles”. In: New York J. Math. 27 (2021), pp. 296–318. arXiv: 1912.07411.

[Dra15]

Alexander Dranishnikov. “On topological complexity of twisted products”. In: Topology Appl. 179 (2015), pp. 74–80. arXiv: 1312.0170. url: https://doi.org/10.1016/j.topol.2014.08.017.

[Far03]

Michael Farber. “Topological complexity of motion planning”. In: Discrete Comput. Geom. 29.2 (2003), pp. 211–221. arXiv: math/0111197. url: http://dx.doi.org/10.1007/s00454-002-0760-9.

[Fer+18]

D. Fernández-Ternero, E. Macías-Virgós, E. Minuz, and J. A. Vilches. “Discrete topological complexity”. In: Proc. Amer. Math. Soc. 146.10 (2018), pp. 4535–4548. arXiv: 1706.02894. url: https://doi.org/10.1090/proc/14122.

[FG07]

Michael Farber and Mark Grant. “Symmetric motion planning”. In: Topology and robotics. Vol. 438. Contemp. Math. Providence, RI: Amer. Math. Soc., 2007, pp. 85–104. arXiv: math/0610857. url: http://dx.doi.org/10.1090/conm/438/08447.

[FTY03]

Michael Farber, Serge Tabachnikov, and Sergey Yuzvinsky. “Topological robotics: motion planning in projective spaces”. In: Int. Math. Res. Not. 34 (2003), pp. 1853–1870. arXiv: math/0210018. url: http://dx.doi.org/10.1155/S1073792803210035.

[FV18]

Lucía Fernández Suárez and Lucile Vandembroucq. “Q-topological complexity”. In: Topological complexity and related topics. Vol. 702. Contemp. Math. Amer. Math. Soc., [Providence], RI, [2018] ©2018, pp. 103–120. arXiv: 1701.05845. url: https://doi.org/10.1090/conm/702/14110.

[FY04]

Michael Farber and Sergey Yuzvinsky. “Topological robotics: subspace arrangements and collision free motion planning”. In: Geometry, topology, and mathematical physics. Vol. 212. Amer. Math. Soc. Transl. Ser. 2. Providence, RI: Amer. Math. Soc., 2004, pp. 145–156. arXiv: math/0210115.

[GL09]

Jesús González and Peter Landweber. “Symmetric topological complexity of projective and lens spaces”. In: Algebr. Geom. Topol. 9.1 (2009), pp. 473–494. arXiv: 0809.0816. url: https://doi.org/10.2140/agt.2009.9.473.

[Gon18]

Jesús González. “Simplicial complexity: piecewise linear motion planning in robotics”. In: New York J. Math. 24 (2018), pp. 279–292. arXiv: 1701.07612. url: https://nyjm.albany.edu/j/2018/24-16.html.

[Gou]

Eric Goubault. On directed homotopy equivalences and a notion of directed topological complexity. arXiv: 1709.05702.

[İK22]

Melih İs and İsmet Karaca. “Higher topological complexity for fibrations”. In: Filomat 36.20 (2022), pp. 6885–6896. arXiv: 2107.04465.

[LM]

Wojciech Lubawski and Wacław Marzantowicz. A new approach to the equivariant topological complexity. arXiv: 1303.0171.

[MM20]

E. Macías-Virgós and D. Mosquera-Lois. “Homotopic distance between functors”. In: J. Homotopy Relat. Struct. 15.3-4 (2020), pp. 537–555. arXiv: 1902.06322. url: https://doi.org/10.1007/s40062-020-00269-x.

[MM22]

E. Macías-Virgós and D. Mosquera-Lois. “Homotopic distance between maps”. In: Math. Proc. Cambridge Philos. Soc. 172.1 (2022), pp. 73–93. arXiv: 1810.12591. url: https://doi.org/10.1017/S0305004121000116.

[Pau19]

Amit Kumar Paul. “Higher analogs of simplicial and combinatorial complexity”. In: Topology Appl. 267 (2019), pp. 106859, 12. arXiv: 1905.01440. url: https://doi.org/10.1016/j.topol.2019.106859.

[PS23]

Amit Kumar Paul and Debasis Sen. “Simplicial and combinatorial versions of higher symmetric topological complexity”. In: Topology Appl. 331 (2023), Paper No. 108491, 19. arXiv: 2104.03038. url: https://doi.org/10.1016/j.topol.2023.108491.

[Rud10]

Yuli B. Rudyak. “On higher analogs of topological complexity”. In: Topology Appl. 157.5 (2010), pp. 916–920. arXiv: 0909.1616. url: http://dx.doi.org/10.1016/j.topol.2009.12.007.

[Sho18]

Robert Short. “Relative topological complexity of a pair”. In: Topology Appl. 248 (2018), pp. 7–23. arXiv: 1710.06201. url: https://doi.org/10.1016/j.topol.2018.07.015.

[Sma87]

Steve Smale. “On the topology of algorithms. I”. In: J. Complexity 3.2 (1987), pp. 81–89. url: http://dx.doi.org/10.1016/0885-064X(87)90021-5.

[Tan18]

Kohei Tanaka. “A combinatorial description of topological complexity for finite spaces”. In: Algebr. Geom. Topol. 18.2 (2018), pp. 779–796. arXiv: 1605.06755. url: https://doi.org/10.2140/agt.2018.18.779.