  The Thompson-Higman groups G_{k,i} have a natural generalization to monoids
M_{k,i}, and inverse monoids Inv_{k,i}. We study some structural features of
M_{k,i} and Inv_{k,i} and investigate the computational complexity of decision
problems. The main interest of these monoids is their close connection with
circuits and circuit complexity.
  The maximal subgroups of M_{k,1} are isomorphic to the groups G_{k,j} (1 \leq
j \leq k-1); so we rediscover all the Thompson-Higman groups within M_{k,1}.
  The Green relations \leq_J and \equiv_D of M_{k,1} can be decided in
deterministic polynomial time when the inputs are words over a finite
generating set of M_{k,1}.
  When a circuit-like generating set is used for M_{k,1} then deciding \leq_J
is coDP-complete. The multiplier search problem for \leq_J is
xNPsearch-complete, whereas the multiplier search problems of \leq_R and \leq_L
are not in xNPsearch unless NP = coNP.
  Deciding \equiv_D for M_{k,1} when the inputs are words over a circuit-like
generating set, is \oplus_{k-1}.NP-complete. For Inv_{k,1} over a circuit-like
generating set, deciding \equiv_D is \oplus_{k-1} P-complete.
