12 problems

A finitely generated group is a group generated by finitely many elements, and it has solvable word problem when there is an algorithm deciding whether any word in its generators r…

Let $G$ be a finitely generated group. A strongly aperiodic subshift of finite type (SFT) is an SFT with no periodic configurations. The strongly aperiodic SFT conjecture. $G$ admi…

Let $F$ be a free group with a generating set $4\Sigma4$ partitioned into a visibly pushdown alphabet. The $4\mathbf{VPL}^\exists4$ membership problem asks whether a given element…

Let $G$ be a group and let $H\leq G$ be a subgroup of index $2$. Write $\operatorname{SMON}(K)$ for the submonoid membership problem in a group $K$. Finite-index submonoid membersh…

A Hopfian finitely presented group is a finitely presented group for which every surjective endomorphism is an automorphism; its word problem asks whether a given word represents t…

Let $\mathfrak{A}$ be Adian's procedure, whose indefinite looping is the unresolved case in deciding left divisibility by a letter. An algorithm $\mathfrak{B}$ is the algorithm Adi…

Undecidability conjecture. The uniform epimorphism problem onto the class of all finitely generated virtually Abelian groups is not decidable.

Virtual specialness conjecture. Virtual specialness is an undecidable property of non-positively curved cube complexes.

Let $M$ be a closed, orientable, irreducible $3$-manifold. Algorithmic orientation-reversing symmetry conjecture. There is an algorithm that determines whether $M$ admits an orient…

Fixed-variable tractability conjecture. For each fixed number of variables, the decision problem admits a more tractable decision procedure.

Let $H$ and $G$ be groups, with $H$ nontrivial and $G$ not virtually free. The wreath-product undecidability conjecture. The rational subset membership problem for $H \wr G$ is und…

Let $G$ and $H$ be finitely generated groups. A subgroup or submonoid membership problem is decidable if there is an algorithm that determines, for every input element, whether it…