The Thompson-Higman groups Gk,i have a natural generalization to monoids, called Mk,i, and inverse monoids, called Invk,i. We study some structural features of Mk,i and Invk,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 Mk,1 and Invk,1 are isomorphic to the groups Gk,j (1 ≤ j ≤ k - 1); so we rediscover all the Thompson-Higman groups within Mk,1. Deciding the Green relations ≤J and ≡D of Mk,1, when the inputs are words over a finite generating set of Mk,1, is in P. When a circuit-like generating set is used for Mk,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 Mk,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 Invk,1 over a circuit-like generating set, deciding ≡ D is ⊕k-1P-complete. It is interesting that the little known complexity classes coDP and ⊕k-1•NP play a central role in Mk,1.
|Original language||English (US)|
|Number of pages||34|
|Journal||International Journal of Algebra and Computation|
|State||Published - Feb 2011|
All Science Journal Classification (ASJC) codes
- Green relations
- Thompson-Higman monoids