Abstract
This is the first of two papers devoted to connections between asymptotic functions of groups and computational complexity. In particular, we show how to construct a finitely presented group with NP-complete word problem. One of the main results of this paper states that if a real number $\alpha \ge 4$ is computable in time $\le 2^{2^{Cm}}$ for some constant $C>0$ then $n^\alpha$ is equivalent to (“big O”) to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is $n^{3\alpha/4}$. On the other hand, if $n^\alpha$ is equivalent to the Dehn function of a finitely presented group then $\alpha$ is computable in time $\le 2^{2^{2^{Cm}}}$ for some constant $C$. Being computer in time $T(n0$ means that there exists a Turing machine which, given $n$, computes a binary rational approximation of $\alpha$ with error at most $1/2^{n+1}$ in time at most $T(n)$. This implies that, say, functions $n^{\pi+1}$, $n^{e^2}$ and $n^\alpha$ for all rational numbers $\alpha \ge 4$ are equivalent to Dehn functions of some finitely presented groups and that $n^\pi$ and $n^\alpha$ for all rational numbers $\alpha \ge 3$ are equivalent to the smallest isodiametric functions of finitely presented groups.
Moreover, we describe all Dehn functions of finitely presented groups $\succ n^4$ as time functions of Turing machines modulo two conjectures:
1. Every Dehn function is equivalent to a superadditive function.
2. The square root of the time function of a Turing machine is equivalent to the time function of a Turing machine.
