Solving semidecidable problems in group theory

2 November 2021
Giles Gardam

Group theory is littered with undecidable problems. A classic example is the word problem: there are groups for which there exists no algorithm that can decide if a product of generators represents the trivial element or not. Many problems (the word problem included) are at least semidecidable, meaning that there is a correct algorithm guaranteed to terminate if the answer is "yes", but with no guarantee on how long one has to wait. I will discuss strategies to try and tackle various semidecidable problems computationally using modern solvers for Boolean satisfiability, with the key example being the discovery of a counterexample to the Kaplansky unit conjecture.