Isoperimetric and isodiametric functions of groups

• 成果类型: Article
• 署名作者: Sapir, MV; Birget, JC; Rips, E
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.2307/3597195
• 发表日期: 2002
• 页码: 345-466
• 关键词: word problem; inequalities

摘要

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 greater than or equal to 4 is computable in time less than or equal to 2(2Cm) 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(3alpha/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 less than or equal to 2(22Cm) for some constant C. Being computable in time T(n) 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(e2) and n(alpha) for all rational numbers alpha greater than or equal to 4 are equivalent to Dehn functions of some finitely presented groups and that n(pi) and n(alpha) for all rational numbers alpha greater than or equal to 3 are equivalent to the smallest isodiametric functions of finitely presented groups. Moreover. we describe all Dehn functions of finitely presented groups > 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.