Generic-case complexity, decision problems in group theory and random walks

Simple item page
dc.creatorKapovich, Ilya
dc.creatorMyasnikov, Alexei
dc.creatorSchupp, Paul
dc.creatorShpilrain, Vladimir
dc.date2002-03-22
dc.date2002-06-10
dc.date.accessioned2026-07-07T04:47:15Z
dc.date.available2026-07-07T04:47:15Z
dc.descriptionWe give a precise definition of ``generic-case complexity'' and show that for a very large class of finitely generated groups the classical decision problems of group theory - the word, conjugacy and membership problems - all have linear-time generic-case complexity. We prove such theorems by using the theory of random walks on regular graphs.
dc.descriptionRevised version
dc.identifierhttps://arxiv.org/abs/math/0203239
dc.identifierhttp://arxiv.org/abs/math/0203239
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/63638
dc.subjectGroup Theory
dc.subjectComputational Complexity
dc.subject20F
dc.titleGeneric-case complexity, decision problems in group theory and random walks
dc.typetext

Files

Collections

arXiv