Abstract:
The weakest variant of algorithmic reducibility called Boolean reducibility is considered. For various closed classes $Q$, the partially ordered sets $\mathcal L_Q$ of Boolean degrees are analyzed. It is proved that for many closed classes $Q$ the corresponding sets $\mathcal L_Q$ have no maximal elements. Examples of sufficiently large classes $Q$ are given for which the sets $\mathcal L_Q$ contain uncountably many maximal elements. It is established that for closed classes $T_{01}$ and $S$M the corresponding sets of degrees have uncountably many minimal elements. Bibliogr. 8.
Keywords:Boolean reducibility, closed classes of Boolean functions.