Geometry of relations and computational complexity of groups
April 16, 2014
3:00pm PGH 646
Abstract
Let \(G\) be a group given by a finite presentation in terms of
generators and relations. For every equality \(w=1\) in \(G\), where
\(w\) is a word in the generators, one can construct a planar picture
\(\Delta\) (so called Van Kampen diagram). The edges of \(\Delta\) are
labeled so that the boundary of \(\Delta\) is labeled by \(w\) while
the boundary label of every region of \(\Delta\) is one of the
defining relators. The growth rate of the isoperimetric function of
such diagrams is responsible for the computational complexity of the
word problem in the group \(G\) and its subgroups.
I will give necessary definitions, examples, and discuss the
asymptotic behavior of isoperimetric functions and some other
asymptotic invariants of groups in connections with the complexity of
algorithmic problems for groups. For example (J.Birget, A.Olshanskii,
E.Rips, M.Sapir), the word problem is of time complexity NP in
a finitely generated group \(G\) if and only if \(G\) is a subgroup of
a finitely presented group \(H\) with polynomial isoperimetric
function.
Webmaster University of Houston
---
Last modified: April 11 2016 - 18:14:43