The Thompson-Higman monoids M_k,i: The J-order, the D-relation, and their complexity

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-1P-complete. It is interesting that the little known complexity classes coDP and ⊕_k-1•NP play a central role in M_k,1.