Question 3.1 — (Fast word problem).

Definitions and mathematical statement

Fix the genus $g$, the source's surface convention, and a finite generating set $S$ of $\operatorname{Mod}_g$. The word problem takes a word $w\in(S\cup S^{-1})^*$, of length $n$, and decides whether its represented mapping class is the identity.

Question 3.1 (fast word problem). Is there a subquadratic-time algorithm for this decision problem? With a computational model fixed, a weak precise interpretation asks for worst-case time $T(n)=o(n^2)$; a frequently used stronger interpretation asks for $T(n)=O(n^{2-\varepsilon})$ for some $\varepsilon>0$. The source does not distinguish those meanings. It suggests $O(n\log n)$ as a possible target, motivated by an algorithm for certain strongly relatively hyperbolic groups in [Fa3]. This suggested rate is not asserted as achieved, and the question does not demand proof of an optimal possible complexity. For fixed $g,S$, constants may depend on those choices; the excerpt does not require uniformity as $g$ varies.

The source cites Masur--Minsky, Theorem 1.3 of [MM1], for a weak-hyperbolicity property of mapping class groups. This is retained as its stated motivation, not replaced by an assertion that $\operatorname{Mod}_g$ is a Gromov-hyperbolic group. The exact relative or action-based notion needs the cited context.

The following discussion concerns conjugacy, a different decision problem: given words representing $x,y$, decide whether $hxh^{-1}=y$ for some $h$. The source calls it harder, says Hemion's original algorithm [He] appeared to give no reasonable, even exponential, time bound, proposes biautomaticity as a refinement, and says even a biautomatic structure gives only an exponential conjugacy algorithm. These are historical comments with their source scope; neither current conjugacy complexity nor biautomaticity is asserted as resolved. The mentioned following approach to conjugacy is not included in the record.

Short English statement

Find a subquadratic algorithm deciding whether a word in a fixed mapping class group is trivial. The source suggests $n\log n$, while leaving the complexity model and meaning of subquadratic unspecified; its separate conjugacy discussion is preserved as context.

Sources

• Local UnsolvedMath registry, permanent ID 11000022, source code catalogue entry, Question 3.1, "Fast word problem," PDF page 31. No individual proposer is supplied.
• Farb, Problems on Mapping Class Groups and Related Topics. Supplied URL: https://www.math.uchicago.edu/~farb/papers/mcgbook.pdf; recorded access 2026-07-29; extraction pdf-font-structure. The edited volume contains 329 explicitly typeset headings across contributed chapters, with repeated local numbering disambiguated by page.
• Internal references [Fa3] for the strongly relatively hyperbolic comparison algorithm, Masur--Minsky [MM1], Theorem 1.3, for weak hyperbolicity, and Hemion [He] for the conjugacy algorithm. Full bibliographic entries are not supplied.
• Supplied status partially_solved and PARTIAL-PROGRESS. The summary reports polynomial/quadratic word algorithms and fast practical algorithms, says faster rates and curve-complex geodesic questions remain open, and frames "fastest possible" complexity as unresolved. The original question asks existence of a subquadratic algorithm, not absolute optimality or the curve-complex geodesic problem. These are supplied assessments without a current primary-literature audit. Background status and redistribution terms remain NEEDS_REVIEW. The registry assigns L4 whereas background records default L3.