Isoperimetric Functions of Groups and Computational Complexity of the Word Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We 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$.
47 pages

Keywords

Group Theory, 20

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/77729

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/9811106
 http://arxiv.org/abs/math/9811106

Collections

arXiv