We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.

We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.

We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.

Schöning [14] introduced a notion of helping and suggested the study of the class ${\mathrm{P}}_{\mathrm{help}}\left(𝒞\right)$ of the languages that can be helped by oracles in a given class $𝒞$. Later, Ko [12], in order to study the connections between helping and “witness searching”, introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call $\mathrm{SH}$ which contains all the self-helping classes. We introduce the Helping hierarchy whose levels are...

Schöning [14] introduced a notion of helping and suggested the study of the class ${\mathrm{P}}_{\mathrm{help}}\left(𝒞\right)$ of the languages that can be helped by oracles in a given class $𝒞$. Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...

The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ and ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$, respectively, for short. We prove that: (i) For $k\ge 2$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$.newline (ii) For stochastic matrices : ${\mathrm{𝖨𝖬𝖯}}_{\mathsf{2}}$ belongs to ${\mathrm{TC}}^0$ while, for $k\ge 3$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$. (iii) For any k, ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$ belongs to ${\mathrm{TC}}^0$.