Factorizations of the Thompson-Higman groups, and circuit complexity

Simple item page
dc.creatorBirget, Jean-Camille
dc.date2006-07-14
dc.date.accessioned2026-07-07T07:18:22Z
dc.date.available2026-07-07T07:18:22Z
dc.descriptionWe consider the subgroup lpG_{k,1} of length preserving elements of the Thompson-Higman group G_{k,1} and we show that all elements of G_{k,1} have a unique lpG_{k,1}.F_{k,1} factorization. This applies to the Thompson-Higman group T_{k,1} as well. We show that lpG_{k,1} is a ``diagonal'' direct limit of finite symmetric groups, and that lpT_{k,1} is a k^infinity Pr"ufer group. We find an infinite generating set of lpG_{k,1} which is related to reversible boolean circuits. We further investigate connections between the Thompson-Higman groups, circuits, and complexity. We show that elements of F_{k,1} cannot be one-way functions. We show that describing an element of G_{k,1} by a generalized bijective circuit is equivalent to describing the element by a word over a certain infinite generating set of G_{k,1}; word length over these generators is equivalent to generalized bijective circuit size. We give some coNP-completeness results for G_{k,1} (e.g., the word problem when elements are given by circuits), and #P-completeness results (e.g., finding the lpG_{k,1}.F_{k,1} factorization of an element of G_{k,1} given by a circuit).
dc.description27 pages
dc.identifierhttps://arxiv.org/abs/math/0607349
dc.identifierhttp://arxiv.org/abs/math/0607349
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/114277
dc.subjectGroup Theory
dc.subject20F10, 68Q15
dc.titleFactorizations of the Thompson-Higman groups, and circuit complexity
dc.typetext

Files

Collections

arXiv