The unsolvability of efficiency for groups (Q1307050)

What is the ``smallest'' presentation of a given finitely presented group \(G\)? The notion of efficiency grew out of attempts to answer this question. If \(\langle x\mid r\rangle\) is a presentation for \(G\), then \(|x|-|r|\leq\text{rk}(H_1(G))-d(H_2(G))\) (here \(\text{rk}(-)\) and \(d(-)\) denote the torsion-free rank and the minimal number of generators, respectively). A group \(G\) is termed efficient if this bound is attained for some presentation. It is known that not all finitely presented groups are efficient. The main point of the paper is to show that efficiency is an algorithmically undecidable property for finitely presented groups (although it is not a Markov property). The elegant proof uses a translation of the efficiency property into a 2-dimensional topological setting (Cockroft properties) and spherical pictures (or diagrams).