Markus Pfeiffer

Proving finitely presented groups to be hyperbolic in polynomial time

… is of course impossible: It is undecidable whether a finitely presented group is hyperbolic. “So, why bother?”, you might think. One response is “Because we want to know!”

Small cancellation techniques have successfully been applied to determine hyperbolicity of finitely presented groups.

We present an algorithm (and its implementation) due to Parker, Neunhöffer, Holt, Linton, Roney-Dougal, and others, which generalises small cancellation and terminates in polynomial time and either proves hyperbolicity (and even gives a word-problem solver), or provides evidence for why it was not able to prove it.