2002/09/01 by Mark Sapir, Jean-Camille Birget, Eliyahu Rips · 4 citations
Mathematics · Computer Science · #Geometric and Algebraic Topology #semigroups and automata theory #Mathematical Dynamics and Fractals #Isoperimetric inequality #Mathematics #Combinatorics
paper · doi:10.2307/3597195
openalex publication_date 2002/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
This is the first of two papers devoted to connections between asymptotic functions of groups and computational complexity. One of the main results of this paper states that if for every m the first m digits of a real number α ≥ 4 are computable in time ≤ C2 2Cm for some constant C> 0 then n α is equivalent (“big O”) to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is n 3/4α. On the other hand if n α is equivalent to the Dehn function of a finitely presented group then the first m digits of α are computable in time ≤ C2 22Cm for some constant C. This implies that, say, functions n π+1, n e2 and n α for all rational numbers α ≥ 4 are equivalent to the Dehn functions of some finitely presented group and that n π and n α for all rational numbers α ≥ 3 are equivalent to the smallest isodiametric functions of finitely presented groups.