Abstract
Byline: JEAN-CAMILLE BIRGET The Thompson--Higman groups G.sub.k,i have a natural generalization to monoids, called M.sub.k,i, and inverse monoids, called Inv.sub.k,i. We study some structural features of M.sub.k,i and Inv.sub.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.sub.k,1 and Inv.sub.k,1 are isomorphic to the groups G.sub.k,j (1 [less-thank or equal to] j [less-thank or equal to] k - 1); so we rediscover all the Thompson--Higman groups within M.sub.k,1. Deciding the Green relations $\leq_{\mathcal J}$ and $\equiv_{\mathcal D}$ of M.sub.k,1, when the inputs are words over a finite generating set of M.sub.k,1, is in P. When a circuit-like generating set is used for M.sub.k,1 then deciding $\leq_{\mathcal J}$ is coDP-complete (where DP is the complexity class consisting of differences of sets in NP). The multiplier search problem for $\leq_{\mathcal J}$ is xNPsearch-complete, whereas the multiplier search problems of $\leq_{\cal R}$ and $\leq_{\cal L}$ are not in xNPsearch unless NP = coNP. The class of search problems xNPsearch is introduced as a slight generalization of NPsearch. Deciding $\equiv_{\mathcal D}$ for M.sub.k,1 when the inputs are words over a circuit-like generating set, is [circled plus].sub.k-1acentsNP-complete; for any h >= 2, [circled plus].sub.hacentsNP is a modular counting complexity class, whose verification problems are in NP. Related problems for partial circuits are the image size problem (which is # acents NP-complete), and the image size modulo h problem (which is [circled plus].sub.hacentsNP-complete). For Inv.sub.k,1 over a circuit-like generating set, deciding $\equiv_{\mathcal D}$ is [circled plus].sub.k-1P-complete. It is interesting that the little known complexity classes coDP and [circled plus].sub.k-1acentsNP play a central role in M.sub.k,1.