Isoperimetric and isodiametric functions of groups
Isoperimetric and isodiametric functions of groups
复制标题
DOI：
10.2307/3597195
复制
发表时间：
1998-11
影响因子：
4.9
通讯作者：
M. Sapir;J. Birget;E. Rips
中科院分区：
文献类型：
--
作者：
M. Sapir;J. Birget;E. Rips
这是致力于群渐近函数与计算复杂性之间联系的两篇论文中的第一篇。特别是，我们展示了如何通过 NP 完全问题构建有限呈现群。本文的主要结果之一指出，如果实数 cx > 4 在时间 0 内可计算，则 na 相当于（“大 O”）有限呈现群的 Dehn 函数。该群的最小等径函数是n3°8/4。另一方面，如果 na 等价于有限呈现群的 Dehn 函数，则 oe 在时间 4 内可计算，相当于某些有限呈现群的 Dehn 函数，并且所有有理数 oe > 3 的 n1r 和 na 等价于有限呈现群的最小等径函数。此外，我们将有限呈现群 F n4 的所有 Dehn 函数描述为图灵机对两个猜想取模的时间函数：
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 cx > 4 is computable in time 0 then na is equivalent ( "big O" ) to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is n3°8/4. On the other hand, if na is equivalent to the Dehn function of a finitely presented group then oe is computable in time 4 are equivalent to Dehn functions of some finitely presented groups and that n1r and na for all rational numbers oe > 3 are equivalent to the smallest isodiametric functions of finitely presented groups. Moreover, we describe all Dehn functions of finitely presented groups F n4 as time functions of Turing machines modulo two conjectures: