Circuits, coNP-completeness, and the groups of Richard Thompson

Simple item page
dc.creatorBirget, Jean-Camille
dc.date2003-10-21
dc.date.accessioned2026-07-07T05:02:08Z
dc.date.available2026-07-07T05:02:08Z
dc.descriptionWe construct a finitely presented group with coNP-complete word problem, and a finitely generated simple group with coNP-complete word problem. These groups are represented as Thompson groups, hence as partial transformation groups of strings. The proof provides a simulation of combinational circuits by elements of the Thompson-Higman group G_{3,1}.
dc.description73 pages
dc.identifierhttps://arxiv.org/abs/math/0310335
dc.identifierhttp://arxiv.org/abs/math/0310335
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/68940
dc.subjectGroup Theory
dc.subject20F10, 68Q15
dc.titleCircuits, coNP-completeness, and the groups of Richard Thompson
dc.typetext

Files

Collections

arXiv