## Abstract

The Thompson-Higman groups G_{k,i} have a natural generalization to monoids, called M_{k,i}, and inverse monoids, called Inv_{k,i}. We study some structural features of M_{k,i} and Inv_{k,i} and investigate the computational complexity of related decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity. The maximal subgroups of M_{k,1} and Inv_{k,1} are isomorphic to the groups G_{k,j} (1 ≤ j ≤ k - 1); so we rediscover all the Thompson-Higman groups within M_{k,1}. Deciding the Green relations ≤J and ≡D of M_{k,1}, when the inputs are words over a finite generating set of M_{k,1}, is in P. When a circuit-like generating set is used for M_{k,1} then deciding ≤ J is coDP-complete (where DP is the complexity class consisting of differences of sets in NP). The multiplier search problem for ≤ J is xNPsearch-complete, whereas the multiplier search problems of ≤ R and ≤ L are not in xNPsearch unless NP = coNP. The class of search problems xNPsearch is introduced as a slight generalization of NPsearch. Deciding ≡ D for M_{k,1} when the inputs are words over a circuit-like generating set, is ⊕ _{k-1}•NP-complete; for any h < 2, ⊕_{h}•NP is a modular counting complexity class, whose verification problems are in NP. Related problems for partial circuits are the image size problem (which is # • NP-complete), and the image size modulo h problem (which is ⊕_{h}•NP-complete). For Inv_{k,1} over a circuit-like generating set, deciding ≡ D is ⊕_{k-1}P-complete. It is interesting that the little known complexity classes coDP and ⊕_{k-1}•NP play a central role in M_{k,1}.

Original language | English (US) |
---|---|

Pages (from-to) | 1-34 |

Number of pages | 34 |

Journal | International Journal of Algebra and Computation |

Volume | 21 |

Issue number | 1-2 |

DOIs | |

State | Published - Feb 2011 |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- Green relations
- Thompson-Higman monoids
- complexity

## Fingerprint

Dive into the research topics of 'The Thompson-Higman monoids M_{k,i}: The J-order, the D-relation, and their complexity'. Together they form a unique fingerprint.