RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2013 Volume 20, Issue 2, Pages 88–101 (Mi da728)

This article is cited in 1 paper

On maximal and minimal elements in partially ordered sets of Boolean degrees

S. S. Marchenkov

Lomonosov Moscow State University, Moscow, Russia

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.

UDC: 519.71

Received: 29.05.2012


 English version:
Journal of Applied and Industrial Mathematics, 2013, 7:4, 549–556

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024