Mathematics – Group Theory
Scientific paper
1998-11-18
Mathematics
Group Theory
107 pages
Scientific paper
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 $\alpha\ge 4$ are computable in time $\le C2^{2^{Cm}}$ for some constant $C>0$ then $n^\alpha$ is equivalent (``big O'') to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is $n^{3/4\alpha}$. On the other hand if $n^\alpha$ is equivalent to the Dehn function of a finitely presented group then the first $m$ digits of $\alpha$ are computable in time $\le C2^{2^{2^{Cm}}}$ for some constant $C$. This implies that, say, functions $n^{\pi+1}$, $n^{e^2}$ and $n^\alpha$ for all rational numbers $\alpha\ge 4$ are equivalent to the Dehn functions of some finitely presented group 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: \begin{enumerate} \item Every Dehn function is equivalent to a superadditive function. \item The square root of the time function of a Turing machine is equivalent to the time function of a Turing machine. \end{enumerate}
Birget Jean-Camille
Rips Eliyahu
Sapir Mark
No associations
LandOfFree
Isoperimetric and isodiametric functions of groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Isoperimetric and isodiametric functions of groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Isoperimetric and isodiametric functions of groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-515591