Mathematics – Group Theory
Scientific paper
2006-07-14
Mathematics
Group Theory
27 pages
Scientific paper
We 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).
No associations
LandOfFree
Factorizations of the Thompson-Higman groups, and circuit complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Factorizations of the Thompson-Higman groups, and circuit complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Factorizations of the Thompson-Higman groups, and circuit complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-97260