Functions on groups and computational complexity

Simple item page
dc.creatorBirget, Jean-Camille
dc.date2002-02-13
dc.date.accessioned2026-07-07T04:46:26Z
dc.date.available2026-07-07T04:46:26Z
dc.descriptionWe give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd-Coxeter radius, filling length functions, etc.), and we study the relation between those functions and the computational complexity of the word problem (deterministic time, nondeterministic time, symmetric space). We show that the isoperimetric function can always be linearly decreased (unless it is the identity map). We present a new proof of the Double Exponential Inequality, based on context-free languages.
dc.identifierhttps://arxiv.org/abs/math/0202124
dc.identifierhttp://arxiv.org/abs/math/0202124
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/63333
dc.subjectGroup Theory
dc.subject20F10, 68Q15
dc.titleFunctions on groups and computational complexity
dc.typetext

Files

Collections

arXiv