Isoperimetric Functions of Groups and Computational Complexity of the Word Problem

Simple item page
dc.creatorBirget, J. -C.
dc.creatorOlshanskii, A. Yu.
dc.creatorRips, E.
dc.creatorSapir, M.
dc.date1998-11-18
dc.date.accessioned2026-07-07T05:26:54Z
dc.date.available2026-07-07T05:26:54Z
dc.descriptionWe prove that the word problem of a finitely generated group $G$ is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgroup of a finitely presented group $H$ with polynomial isoperimetric function. The embedding can be chosen in such a way that $G$ has bounded distortion in $H$.
dc.description47 pages
dc.identifierhttps://arxiv.org/abs/math/9811106
dc.identifierhttp://arxiv.org/abs/math/9811106
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/77729
dc.subjectGroup Theory
dc.subject20
dc.titleIsoperimetric Functions of Groups and Computational Complexity of the Word Problem
dc.typetext

Files

Collections

arXiv