1 Introduction
Many problems with monotone Boolean functions (MBFs) appear in logical and physical level design of systems (Aslanyan et al., 2019), but also in artificial intelligence (Aslanyan and Sahakyan, 2009), data science and computational learning theory (Aslanyan et al., 2023a), hypergraph theory (Sahakyan, 2023; Sahakyan and Aslanyan, 2017) and other areas (e.g. Carlet et al., 2016; Kulhandjian et al., 2019; Crawford-Kahrl et al., 2022; Kabulov and Berdimurodov, 2021; Zhang et al., 2022). MBFs are used to encode extremely important constructions in various combinatorial optimizations providing a natural way of describing compatible subsets of sets of finite constraints (see e.g. Aslanyan et al., 2023b; Tennakoon et al., 2021; Damásdi et al., 2021).
Let there be n independent constraints in an optimization problem with a target function $\nu (\alpha )$, $\alpha \in P([n])$, where $[n]=\{1,2,\dots ,n\}$, and $P([n])$ is the power set of $[n]$; α encodes a subset of constraints, and the values of ν are valid only on compatible subsets. Sometimes the compatibility check of subsets α becomes a separate intractable problem. The question how to minimize the checks/tests in a global optimization procedure arises naturally. Obviously, if there is a compatible subset ${\alpha _{1}}$ given, and ${\alpha _{2}}\subseteq {\alpha _{1}}$, then ${\alpha _{2}}$ is compatible. The overall structure of compatibility is given by these inclusions and then by monotone Boolean functions, and the idea behind the recognition of these functions is to find the maximum compatible subsets of constraints, applying fewer checks and procedures in the optimality search processes.
A number of applications (e.g. wireless sensor networks, dead-end tests of tables, data mining) (Kovalerchuk and Delizy, 2005; Kulhandjian et al., 2019; Aslanyan and Sahakyan, 2009; Aslanyan et al., 2019) use optimization with MBF, where MBFs are represented by hypercube constructions such as chains and anti-chains (Freixas, 2022; Griggs et al., 2023). Other similar applications with MBF can be added to this list (Clements, 1973; Tennakoon et al., 2021; Damásdi et al., 2021; Carlet et al., 2016).
There is a number of known effective tools and methods for analysing MBFs (Korobkov, 1965; Hansel, 1966; Tonoyan, 1979; Gainanov, 1984) and new approaches are constantly being sought, investigated, and applied (e.g. Carlet et al., 2016; Boros and Hammer, 2002; Lange and Vasilyan, 2023; Sahakyan et al., 2022; Balogh et al., 2021; Bezrukov et al., 2023). Open problems in this area include the reconstruction problem of bounded classes of Boolean functions with randomization of queries and functions, and the use of cube-splitting and chain-splitting technique of the Boolean domain (Blum, 2003; Jackson et al., 2011; O’Donnell and Servedio, 2005; Aslanyan and Sahakyan, 2017; Black et al., 2023; Boros et al., 1991).
A well-known approach concerning MBFs recognition is query-based identification – recognition of an unknown MBF of n variables using an oracle and membership queries to it. Hansel’s algorithm (Hansel, 1966), based on partitioning the binary cube into a special set of non-intersecting chains, provides optimal reconstruction in the sense of Shannon complexity for the whole class of MBFs. In practical algorithmic implementations, it is even not necessary to build and store all Hansel chains in computer memory (Tonoyan, 1979), which solves the memory limitation problem in applications. But the computational complexity remains.
In order to obtain solutions for bounded classes of MBFs, it is necessary to find a way to the structural properties of these classes (Braverman et al., 2022; Chao and Yu, 2023; Lovász, 2007). The research objective of this paper is related to the well-known Kruskal-Katona theorem (Kruskal, 1963; Katona, 1968, 1987; Sales and Schülke, 2022; Frankl and Katona, 2021), and the class of $\textit{KK-MBF}$ functions, related to this theorem, which describes the exact optimal monotone constructions of shadow minimization (constraint minimization) (Braverman et al., 2022; Chao and Yu, 2023; Jung, 2023; Madden, 2023) and existence of Sperner systems for a given set of parameters. In this way, $\textit{KK-MBF}$ class of MBFs becomes a special and attractive class for recognition, and this is the theoretical value of $\textit{KK-MBF}$ recognition. On the other hand, the practical value of $\textit{KK-MBF}$ recognition consists in the following. $\textit{KK-MBF}$s appear when compatibility is not only controlled by the inclusion of subsets of constraints. Suppose we are given two constrained, k-subsets ${\alpha _{1}}$ and ${\alpha _{2}}$, such that ${\alpha _{2}}$ alphabetically proceeds ${\alpha _{1}}$. In some applications, constraint compatibility should have the following property: compatibility of ${\alpha _{2}}$ is a simple consequence of the compatibility of ${\alpha _{1}}$ because of the alphabetical priorities of constraints. In this case, the structure of constraint compatibility is given by $\textit{KK-MBF}$ functions.
In this research, we investigate the $\textit{KK-MBF}$ class, focusing on query-based recognition algorithms. Example subclasses of the class are also presented and discussed.
The rest of the paper is organized as follows. Section 2 provides necessary definitions, preliminaries, and basic concepts. The $\textit{KK-MBF}$ class, its basic properties/constraints, as well as recognition procedures, are introduced in Section 3. Section 4 discusses the cardinality issues of the class. Special subclasses are considered in Section 5. The paper ends with the concluding remarks.
2 Preliminaries
2.1 Monotone Boolean Function Recognition
Let ${B^{n}}=\{({x_{1}},\dots ,{x_{n}})\hspace{0.1667em}|\hspace{0.1667em}{x_{i}}\in \{0,1\},\hspace{2.5pt}i=1,\dots ,n\}$ denote the set of vertices of the n-dimensional binary (unit) cube. Let ${\alpha =(\alpha _{1}},\dots ,{\alpha _{n}})$ and ${\beta =(\beta _{1}},\dots ,{\beta _{n}})$ be two vertices of ${B^{n}}$. α precedes β (by component-wise order), denoted as $\alpha \preccurlyeq \beta $, if and only if ${\alpha _{i}}\leqslant {\beta _{i}}$ for $1\leqslant i\leqslant n$. α and β are comparable if $\alpha \preccurlyeq \beta $ or $\beta \preccurlyeq \alpha $, otherwise, they are incomparable. A set of incomparable vertices in ${B^{n}}$ is also called a Sperner family. A set $\{{\alpha ^{1}},\dots ,{\alpha ^{k}}\}$ of elements of ${B^{n}}$ is a growing chain if ${\alpha ^{i}}\prec {\alpha ^{j}}$ for $1\leqslant i\lt j\leqslant k$. A chain is simple if ${\alpha ^{i}}\prec {\alpha ^{j}}$ and there is no ${\alpha ^{r}}$ such that ${\alpha ^{i}}\prec {\alpha ^{r}}\prec {\alpha ^{j}}$.
The serial number of the vertex $\alpha =({a_{1}},\dots ,{a_{n}})$ is the natural number ${a_{1}}{2^{n-1}}+{a_{2}}{2^{n-2}}+\cdots +{a_{n}}{2^{0}}$, whose binary representation is ${a_{1}}{a_{2}}\dots {a_{n}}$.
We will also use the lexicographic order of vertices: α precedes β lexicographically ($\alpha {\preccurlyeq _{\text{lex}}}\beta $) if either there exists an integer k, $1\leqslant k\leqslant n$, such that ${a_{k}}\lt {b_{k}}$ and ${a_{i}}={b_{i}}$ for $i\lt k$, or $\alpha =\beta $.
In literature there are different, sometimes confusing definitions of lexicographic order (Schröder, 2016). Mathematical definition is set-theoretical that uses the value 1 to code the presence of an element in a subset: $x{\lt _{\text{lex}}}y$ if $\min (x\Delta y)\in x$. Appearance of elements in a subset is coded by a binary vector, and vector α precedes vector β when α precedes β alphabetically. Here $1\lt 0$. When we apply to combinatorial settings, the hypercube is considered, and lexicographical order of vertices of ${B^{n}}$, defined alphabetically, uses relation $0\lt 1$. We will use the standard set-theoretical definition indicated as $\textit{lex}$ in Fig. 1. $\textit{revlex}$ is the reverse of this, i.e. $(00000,00001,\dots ,11111)$. $\textit{colex}$ in set-theoretical settings means: $x{\lt _{\textit{co-lex}}}y$ if $\max (x\Delta y)\in y$. This is convenient when we add a new dimension to the vectors intending to continue the ordered sequence when the initial segment remains unchanged. But as we see in Fig 1, $\textit{colex}$, unlike the $\textit{lex}$ or $\textit{revlex}$, preserves neither the order of numerical values nor the order on the layers of the hypercube graphically, in the Hasse diagram. The $\textit{sim}$ (simplicial) order lists hypercube vertices layer after the layer (see the next page for the concept of a layer); in each layer, vertices are ordered according to their serial number. We will use the $\textit{revlex}$ basically, but when there is no confusion we will refer to it simply as $\textit{lex}$.
Lexicographic, co-lexicographic and simplicial orders are shown in Fig. 1 on the set of vertices of ${B^{5}}$.
Fig. 1
Lexicographic, co-lexicographic and simplicial orders of vertices of ${B^{5}}$. The sign # marks the natural order which coincides with the numerical value of binary representation of vertices.
We define also partition/splitting of ${B^{n}}$ into two $(n-1)$-dimensional sub-cubes according to the values of the binary variables; for arbitrary ${x_{i}}$:
\[\begin{aligned}{}& {B_{{x_{i}}=0}^{n-1}}=\big\{({x_{1}},\dots ,{x_{n}})\in {B^{n}}\hspace{0.1667em}\big|\hspace{0.1667em}{x_{i}}=0\big\}\hspace{1em}\text{and}\\ {} & {B_{{x_{i}}=1}^{n-1}}=\big\{({x_{1}},\dots ,{x_{n}})\in {B^{n}}\hspace{0.1667em}\big|\hspace{0.1667em}{x_{i}}=1\big\}.\end{aligned}\]
Any subset ${\mathcal{M}\subseteq B^{n}}$ will be partitioned into
\[ {\mathcal{M}_{{x_{i}}=1}}\subseteq {B_{{x_{i}}=1}^{n-1}},\hspace{1em}\text{and}\hspace{1em}{\mathcal{M}_{{x_{i}}=\hspace{0.1667em}0}}\subseteq {B_{{x_{i}}=\hspace{0.1667em}0}^{n-1}}.\]
${B^{n}}$ can also be partitioned according to a set of variables. Partitioning according to variables ${x_{{i_{1}}}},\dots ,{x_{{i_{k}}}}$, we get ${2^{k}}$ number of $(n-k)$-dimensional sub-cubes, where in each of them the values of ${x_{{i_{1}}}},\dots ,{x_{{i_{k}}}}$ are fixed in an appropriate way; for example,
Figure 2 illustrates the split of the ${B^{6}}$ according to two variables.
Let ${L_{k}}=\big\{({x_{1}},\dots ,{x_{n}})\in {B^{n}}\hspace{0.1667em}\big|\hspace{0.1667em}{\textstyle\sum _{i=1}^{n}}{x_{i}}=k\big\}$. We call ${L_{k}}$ the k-th layer of ${B^{n}}$.
The shadow ${\delta ^{i}}\mathcal{M}$ of ${\mathcal{M}\subseteq B^{n}}$ is the set of vertices of ${L_{i}}$, which are less than some vertex of $\mathcal{M}$.
In case all the vertices of $\mathcal{M}$ are from the same layer, e.g. from the k-th layer, the lower (upper, respectively) shadow of $\mathcal{M}$ is ${\delta ^{k-1}}\mathcal{M}$ (${\delta ^{k+1}}\mathcal{M}$, respectively), i.e. the set of vertices from the $(k-1)$-th layer, which are less than some vertex of $\mathcal{M}$ (from the $(k+1)$-th layer, which are greater than some vertex of $\mathcal{M}$, respectively).
Boolean function $f:{B^{n}}\to \{0,1\}$ is called monotone if for every two vertices $\alpha ,\beta \in {B^{n}}$, if $\alpha \prec \beta $, then $f(\alpha )\leqslant f(\beta )$. Vertices of ${B^{n}}$, where f takes the value “1”, are called units or true points of the function; vertices, where f takes the value “0”, are called zeros or false points of the function. ${\alpha ^{1}}$ is a lower unit (or minimal true point) of the function if ${f(\alpha ^{1}})=1$, and $f(\alpha )=0$ for every $\alpha \in {B^{n}}$, such that $\alpha {\prec \alpha ^{1}}$. ${\alpha ^{0}}$ is an upper zero (or maximal false point) of the function if ${f(\alpha ^{0}})=0$, and $f(\alpha )=1$ for every $\alpha \in {B^{n}}$ such that ${\alpha ^{0}}\prec \alpha $. $\min T(f)$ and $\max F(f)$ denote the sets of minimal true points and maximal false points, respectively. Obviously, $\min T(f)$ and $\max F(f)$ are Sperner families in ${B^{n}}$.
Formally, the work with MBFs started in 1897, with the issue of counting their number (Dedekind, 1895). The first algorithmic and complexity-related considerations belong to Korobkov (1965), where, in particular, the valuable concept of resolving subsets was introduced. The final asymptotic estimate about the number of MBFs of n variables was obtained in Korshunov (1981, 2003). The technique on how to introduce and analyse MBFs, is basically presented in Hansel (1966), Korshunov (2003), Lovász (2007).
The Hansel chain structure (Hansel, 1966) was invented in 1966 and played one of the central roles in MBF-related algorithmic techniques.
The next valuable step towards this was taken by Tonoyan (1979), who introduced a set of simple procedures (chain algebra) that serve all the actual queries about Hansel chains, providing a technical solution to all the problems related to algorithms with Hansel chains, without constructing and keeping them in computer memory. A slightly modified and simplified version of Sokolov (1987) is presented using tools such as: enumeration of all chains, and a procedure of finding the i-th vertex of the j-th chain.
A recurrent step of constructing Hansel chains in ${B^{n}}$ is the following (illustrated graphically in Fig. 3). Let ${l_{0}}$ be an arbitrary chain in ${B_{{x_{n}}=0}^{n-1}}$, and let ${l_{1}}$, geometrically, be the same chain in ${B_{{x_{n}}=1}^{n-1}}$. Thorough the chain constructions, all pairs of chains like ${l_{0}}$ and ${l_{1}}$ are modified according the following rule. Chain ${l_{1}}$ is shortened by removing the last edge ${(\alpha ^{\prime }_{1}},{\alpha ^{\prime }_{2}})$ from it, and chain ${l_{0}}$ is updated by adding a new edge $({\alpha _{2}},{\alpha ^{\prime }_{2}})$ to it. This construction provides one of the basic properties of Hansel chains in ${B^{n}}$: the relative complement of three consecutive vertices of extended chain ${l^{\prime }_{0}}$ belongs to the shortened chain ${l^{\prime }_{1}}$. Relative complement is a vertex α, that together with the growing chain of tree consecutive vertices ${\alpha _{1}}$, ${\alpha _{2}}$, ${\alpha _{3}}$ composes a subcube of dimension 2.
We aim at extending this picture of chain-split to the lexicographic order of vertices in ${B^{n}}$. At least, we note that the longest Hansel chain corresponds to the chain consisting of the first vertices of layers of ${B^{n}}$ under the lexicographic ordering. The mirrored chain of the last vertices under the lexicographic ordering will be considered as well.
In the MBF recognition problem using membership queries, the overall goal is to determine an unknown MBF of n variables using as few oracle queries (or tests) as possible. The function can be fully recognized by finding all its upper zeros (and/or lower units) (Korobkov, 1965). The Shannon complexity of finding all upper zeros (lower units) of an arbitrary monotone Boolean function of n variables is ${C_{n}^{\lfloor n/2\rfloor }}+{C_{n}^{\lfloor n/2\rfloor +1}}$ (Hansel, 1966).
Another recognition structure is used in Sokolov (1987) and in its extensions. For even n, ${B^{n}}$ is split according to two variables and the recognition starts in the two middle layer sub-cubes of this construction. For odd n, firstly ${B^{n}}$ is split according to one variable, then as each sub-cube now has an even size, the procedure for even sizes is applied. This provides optimal recognition of all MBFs in the sense of Shannon complexity. Unfortunately, while simple and attractive, this approach cannot be used as a practical algorithm. Finally, it is worth to mention the work (Gainanov, 1984) that considers not the Shannon complexity, but the individual complexity of MBF given by its resolving set size.
2.2 Constraint Monotone Boolean Function Recognition
In general, tasks related to the recognition of MBFs may have different formulations. One objective is to recognize a particular unknown function, knowing that it belongs to the class of MBFs or to one of its subclasses. Another goal is to start with partial knowledge about the unknown function, trying to complete the information. One more case is when the number of queries is restricted by some number k and the goal is to maximize the recognized part of the function (Sahakyan et al., 2022). Similar problems can be formulated for specific classes of Boolean functions. Examples of classes are as follows:
KK-MBF Kruskal-Katona MBFs arise as a result of the shadow minimization theorem (Kruskal, 1963; Katona, 1968, 1987). $\textit{KK-MBF}$s are monotone Boolean functions but they also intersect the cube layers along their initial segments of the lexicographic order. The complement of the $\textit{KK-MBF}$ area in ${B^{n}}$ has a similar property; it is related to the initial segments of the reverse-lexicographic order, and they are anti-monotone.
Symmetric MBF This is a trivial class of functions that takes a constant value on the cube layers. Trivial, but these functions are practically important. Examples are majority functions, parity functions, and others (Nosov, 2023).
Threshold MBF Functions are defined by a linear inequality of weighted sums of variables.
Matroid MBF Monotone Boolean function f is called a matroid function if for each $\alpha ,\beta \in \min T(f)$ with ${\alpha _{i}}=1$, ${\beta _{i}}=0$, there exists a coordinate j with ${\alpha _{j}}=0$, ${\beta _{j}}=1$ such that vertex ${\alpha ^{\prime }}$, obtained from α by replacing ${\alpha _{i}}$ with 0 and ${\alpha _{j}}$ with 1, belongs to $\min T(f)$.
The combinatorial complexity of reconstruction in these and other subclasses of MBFs is not well studied. For example, monotone Boolean functions, with zeros and units separated by two middle layers of the cube, are the most difficult functions for query-based reconstruction when only the monotonicity of the function is given. But if it is known that the function belongs to the class of symmetric functions, the reconstruction of this function can be done by n queries. The same function also belongs to the $\textit{KK-MBF}$ class. Knowing more MBF cases that are practically reconstructible enables system proctoring and application problem solving.
3 KK-MBF Recognition
In this section, we consider a special class of monotone Boolean functions, related to the well-known Kruskal-Katona theorem, which describes the exact optimal monotone constructions of shadow minimization (constraint minimization) problem, and the existence problem of Sperner systems for a given set of parameters. Although the reconstruction problem for general MBFs is intractable, the problem itself is extremely important in system design and implementation. The reconstruction problem for such subsets of MBFs is insufficiently investigated, and in this paper, for the first time in our knowledge, the problem of recognition of functions of class $\textit{KK-MBF}$ is investigated.
3.1 Introduction to KK-MBF Type Functions
Definition 1.
Let f be a monotone Boolean function on ${B^{n}}$. f is called a $\textit{KK-MBF}$ type function if zeros of f on the layers of ${B^{n}}$ compose initial segments of the reverse-lexicographic order (an example is given in Fig. 4, where uncoloured vertices correspond to zeros of the function).
The initial formulations of the shadow theorem in Kruskal (1963), Katona (1968, 1987) are given in terms of co-lexicographic order, but this framework was later simplified to the simple lexicographic ordering (Aslanyan, 1979). The basic result was obtained for two neighbour layers of the cube. The name $\textit{KK}$ now refers to an extension of the basic result of the shadow minimization theorem to many layers of ${B^{n}}$, as well as to results on the existence of Sperner families (Clements, 1973; Daykin et al., 1974). Usually, a $\textit{KK-MBF}$ function f is given through its characteristics, $\mathrm{\# }\min T(f)=\langle {p_{{i_{1}}}},{p_{{i_{2}}}},\dots ,{p_{{i_{r}}}}\rangle $, where ${p_{{i_{j}}}}$ is the number of lower units of f on the ${i_{j}}$-th layer. An example is given in Fig. 4.
3.2 Resolving Sets for KK-MBF
First, let us introduce some general concepts from the field of reconstruction of Boolean functions (Korobkov, 1965). Suppose we are given a certain class $\mathcal{S}$ of Boolean functions and $f\in \mathcal{S}$.
It follows from the definition that to reconstruct a function it is sufficient to determine its values on some of its resolving sets.
A resolving set $G(f,\mathcal{S})$ is called a deadlock resolving set for $(f,\mathcal{S})$, if no subset of it is resolving for the pair $(f,\mathcal{S})$.
When $\mathcal{S}$ is the set of all monotone Boolean functions, then every function $f\in \mathcal{S}$ has a unique deadlock resolving set included in all its resolving sets; this is the set $G(f)=\min T(f)\cup \hspace{0.1667em}\max F(f)$ (Korobkov, 1965). Thus, for a general MBF, the concept of deadlock resolving set is given by the set of all upper zeros and lower units of the function, which represent two interrelated Sperner systems.
It should be noted that this is not true for other Boolean functions and classes, for example, for the class of symmetric Boolean functions there are no unique deadlock resolving sets.
In this section, we investigate the existence of a deadlock resolving set for $\textit{KK-MBF}$ functions.
We formulate two simple properties for $\textit{KK-MBF}$ type functions f and call them horizontal and vertical conditions, denoting them as Cond-h and Cond-v.
Cond-h:
Cond-v:
-
(1) if $f(\alpha )=0$ for a vertex α of some layer ${L_{k}}$, then $f(\beta )=0$ for all $\beta \in {L_{k}}$ reverse-lexicographically preceding α ($\beta {\preccurlyeq _{\text{revlex}}}\alpha $),
-
(2) if $f(\alpha )=1$ for a vertex α of some layer ${L_{k}}$, then $f(\beta )=1$ for all β of ${L_{k}}$ lexicographically preceding α ($\beta {\preccurlyeq _{\text{lex}}}\alpha $).
These conditions, applied recursively, define a domain for each vertex $\alpha \in f$; denote it by $d(f,\alpha )$. Domain is downward when $f(\alpha )=0$ and upward if $f(\alpha )=1$. A simple characterization of the domains can be given in terms of natural order of vertices (their serial numbers).
Proof.
-
• Suppose that $f(\alpha )=1$. Consider the partition ${B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}\cup {B_{{x_{1}}=1}^{n-1}}$ of ${B^{n}}$ by the first variable (see Fig. 4), and apply an inductive inference by the number of variables. Consider 2 cases:
-
1) ${\alpha \in B_{{x_{1}}=1}^{n-1}}$; then, $d(f,\alpha )\subseteq {B_{{x_{1}}=1}^{n-1}}$, and by the induction hypothesis, the proposition is correct.
-
2) ${\alpha \in B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}$; in this case, $d(f,\alpha )\subseteq {B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}\cup {B_{{x_{1}}=1}^{n-1}}$. For the part in ${B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}$, all vertices have higher serial number according to the induction hypothesis. As for the part in ${B_{{x_{1}}=1}^{n-1}}$, the proposition simply follows from the evident fact, that the vertex of the smallest serial number in ${B_{{x_{1}}=1}^{n-1}}$ is$(1\stackrel{n-1}{\overbrace{00\dots 0}})$ (equals to ${2^{n-1}}$), while the vertex of the highest serial number in ${B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}$ is $(0\stackrel{n-1}{\overbrace{11\dots 1}})$ (equals ${2^{n-1}}-1$).
-
-
• Consideration of the case $f(\alpha )=0$ is similar.
Note that not all vertices of ${B^{n}}$ with a higher (smaller) serial number than α, when $f(\alpha )=1$ ($f(\alpha )=0$) are part of the $d(f,\alpha )$.
We also define the notion of corner points for $\textit{KK-MBF}$ type functions.
Definition 3.
Let $z(f)$ denote the set of all zero-corner points, and $o(f)$ denote the set of all one-corner points of function f.
Summarizing all the above reasoning, we formulate the following statement.
Proposition 2.
Every monotone Boolean function f of class $\textit{KK-MBF}$ has a unique deadlock resolving set which is included in all its resolving sets. This deadlock resolving set for f is the set $G(f)=z(f)\cup o(f)$.
Proof.
First note that any zero-corner point α, as a point of $f(\alpha )=0$ has its domain $d(f,\alpha )$ filled with zero values. But as a corner point, $d(f,\alpha )$ cannot be strongly included in any other domain $d(f,\beta )$ of a point with $f(\beta )=0$. So the domain of a zero-corner point α is the deadlock domain filled with zero values. The same note is valid for one-corner points. Now, ${\textstyle\bigcup _{\alpha \in z(f)\cup o(f)}^{}}d(f,\alpha )={B^{n}}$, otherwise, if there exists $\beta \in {B^{n}}$ out of ${\textstyle\bigcup _{\alpha \in z(f)\cup o(f)}^{}}d(f,\alpha )$, then β may generate a new domain, or it will properly include some existing domain in it. It follows that $z(f)\cup o(f)$ is a resolving set. Given that the domains of 0- and 1-corner points cannot intersect by definition, and each point $\alpha \in z(f)\cup o(f)$ is represented only by itself, and by its domain, the proof is complete. □
For a general MBF, it is well-known that $|\hspace{-0.1667em}\min T(f)\cup \max F(f)|$ can reach the value ${C_{n}^{\lfloor n/2\rfloor }}+{C_{n}^{\lfloor n/2\rfloor +1}}$ and as a consequence, recognition of these functions cannot be done with less complexity. Our first notion about the $\textit{KK-MBF}$ recognition complexity is an upper bound obtained for the value $|z(f)\cup o(f)|$. Due to the resolving property of the set $z(f)\cup o(f)$, the estimate will show the number of required tests for reconstruction of $\textit{KK-MBF}$ functions.
Proposition 3.
For monotone Boolean functions f of class $\textit{KK-MBF}$ $|z(f)\cup o(f)|\leqslant 2(n-1)$.
Proof.
According to the condition Cond-h, on each layer of ${B^{n}}$ there can be only one pair α, β of neighbour vertices, for which $f(\alpha )=0$ and $f(\beta )=1$. Theoretically, they also may be corner points; hence, $|z(f)\cup o(f)|\leqslant 2(n+1)$. Exceptionally, on each of the 0-th and n-th layers there can be only 1 corner point, and in these cases $|z(f)\cup o(f)|=1$. Therefore, $|z(f)\cup o(f)|\leqslant 2(n-1)$. □
It is still a question if the value $2(n-1)$ is reachable. A simple view of exercises in Fig. 4 shows that the real number of corner points will be smaller, but at this point we aim at mentioning the big difference between the recognition complexities of general MBF and the $\textit{KK-MBF}$.
Concerning the issue about the size of deadlock resolving sets we may refer to the Theorem 1 of Daykin et al. (1974) and to Clements (1973). Here, parametrized subsets of MBF are considered. Let us suppose that there are given numbers ${p_{0}},{p_{1}},\dots ,{p_{n}}$, denoting the quantities of upper zeros of functions on layers of ${B^{n}}$. Existence theorems of Sperner families, i.e. existence of MBF by the sets $\{{p_{0}},{p_{1}},\dots ,{p_{n}}\}$ are obtained. The first theorem, Daykin et al. (1974), transfers all ${p_{i}}$ to the layers upper the middle layer. The second theorem (Clements, 1973; Daykin et al., 1974) gives the necessary and sufficient condition of existence in terms of a formula based on Kruskal’s cascade properties (Kruskal, 1963).
Similar theorems could be formulated for $\textit{KK-MBF}$, where ${p_{i}}\hspace{2.5pt}\text{s}$ are the numbers of corner points in layers, and then ${p_{i}}\text{s}$ can be either 0 or 1. Thus, the formulas would obtain simpler Kruskal’s cascade forms. But in our case, the upper bound $2(n-1)$ is relatively small and acceptable as a complexity estimation in comparison to ${C_{n}^{\lfloor n/2\rfloor }}+{C_{n}^{\lfloor n/2\rfloor +1}}$. The problem is how to effectively find the mentioned corner points algorithmically.
On the other hand, let us consider a series of $\textit{KK-MBF}$ functions, which provide a lower bound for $|z(f)\cup o(f)|$.
Define corner points on layers as follows:
On the 1st layer we take two corner points: 1-corner point is the vertex $(1\stackrel{n-1}{\overbrace{00\dots 0}})$, the smallest vertex of ${B_{{x_{1}}=1}^{n-1}}$ in $\textit{lex}$ order; and 0-corner point is $(01\stackrel{n-2}{\overbrace{00\dots 0}})$, the smallest vertex of ${B_{{x_{1}}=\hspace{0.1667em}0,{x_{2}}=1}^{n-2}}$ in $\textit{lex}$ order. These are two neighbour vertices on the 1st layer.
On the 2nd layer we construct two corner points as follows: 1-corner point is $(01\stackrel{n-3}{\overbrace{00\dots 0}}1)$, the smallest vertex of the cube ${B_{{x_{1}}=\hspace{0.1667em}0,{x_{2}}=1,{x_{n}}=1}^{n-3}}$; 0-corner point is $(0011\stackrel{n-4}{\overbrace{00\dots 0}})$, the smallest vertex of ${B_{{x_{1}}=\hspace{0.1667em}0,{x_{2}}=\hspace{0.1667em}0,{x_{3}}=1,{x_{4}}=1}^{n-4}}$, all in $\textit{lex}$ order.
This process is continued until one of the constructed subcubes becomes small and we reach a corner point defined by a 0-size subcube, i.e. a vertex.
Let us explain again the construction. Vertex $(1\stackrel{n-1}{\overbrace{00\dots 0}})$ is the smallest vertex on layer 1 of ${B^{n}}$. Vertex $(01\stackrel{n-2}{\overbrace{00\dots 0}})$ is its left neighbour (see Fig. 4). Vertex $(1\stackrel{n-1}{\overbrace{00\dots 0}})$ defines all vertices of ${B_{{x_{1}}=1}^{n-1}}$ as units of the function by Cond-h, and vertex $(01\stackrel{n-2}{\overbrace{00\dots 0}})$ defines as zero only the vertex $(\stackrel{n}{\overbrace{00\dots 0}})$. Upper area of vertex $(01\stackrel{n-2}{\overbrace{00\dots 0}})$ still can be defined arbitrarily – either as a zero or as a unit. But we take the leftmost vertex $(01\stackrel{n-3}{\overbrace{00\dots 0}}1)$ of the layer next to the layer of $(01\stackrel{n-2}{\overbrace{00\dots 0}})$ defining its value as unit. The left neighbour’s value we define as zero. This simple construction, repeated as long as possible, gives a series of $\textit{KK-MBF}$ functions. How many corner points may have these functions?
Starting from the first layer, we reach the last possible corner point on the:
$(n/2)$-th layer, if n is even – in this case we have 2 corner points on each layer starting from 1 to $n/2$; and $(n+1)/2$-th layer, if n is odd – in this case we have 2 corner points on each layer starting from 1 to ($n-1)/2$, and one corner point on the ($n+1)/2$-th layer.
3.3 Identification of KK-MBF Type Functions: Main Procedures
Hansel chain based MBF recognition methods are global tools and can be applied to recognize any class of monotone Boolean functions, including $\textit{KK-MBF}$. However, we aim to exploit specific properties of this class of functions to achieve more efficient recognition. To go beyond the chain-based analysis, in this section we consider the recognition of $\textit{KK-MBF}$ functions at the level of analysis of particular layers of ${B^{n}}$.
A useful step and exercise in recognitions is to determine the first and last nontrivial layers (trivial layers are those with all-zeros or with all units of the function). This can be done considering the following two chains of length n: ${L_{1}}$ that is the chain consisting of all first, and ${L_{2}}$ that is the chain consisting of all last elements of the lexicographic order of layers. ${L_{1}}$ is the longest Hansel chain in the chain split, see Fig. 3. Applying bisections on chains ${L_{1}}$ and ${L_{2}}$, we can find two neighbouring layers $({k_{1}}$, ${k_{1}}+1)$ and $({k_{2}}$, ${k_{2}}+1)$ and vertices on chains ${L_{1}}$ and ${L_{2}}$, respectively, where the function’s value changes from 0 to 1. This means that the layers from ${k_{2}}+1$ to n, and from 0 to ${k_{1}}$ are trivial, they accept values 0 and 1, correspondingly. Indeed, when first vertex of layer ${k_{1}}$ accepts 0, then the whole layer accepts 0. The layer ${k_{1}}$ and below is filled by values 0 (the trivial 0 layers), but in layer ${k_{1}}+1$ there exists at least one vertex with value 1 so that trivial layers interrupt here. Similar explanation is valid concerning the chain ${L_{2}}$. The bisection procedure of each chain requires only ${\log _{2}}(n)$ queries to the oracle.
On the other hand, if the vertices on each layer of ${B^{n}}$ are ordered lexicographically, we can apply layer by layer bisections and find a corner vertex candidate ${\alpha _{k}}$ on the k-th layer with no more than ${\log _{2}}({C_{n}^{k}}+1)$ queries.
In this manner, a $\textit{KK-MBF}$ type function can be recognized by no more than ${\textstyle\sum _{k=1}^{n}}{\log _{2}}({C_{n}^{k}}+1)$ queries. A very rough estimate of this total value would be $O({n^{2}})$, as the largest layer is the middle k-th layer with $k=[n/2]$, where ${C_{n}^{[n/2]}}\sim \frac{{2^{n+1}}}{\sqrt{2\pi n}}$ with $n\to \infty $.
Proposition 4.
Time complexity of reconstruction of monotone Boolean functions of class $\textit{KK-MBF}$ by layer by layer bisections is $O({n^{2}})$.
For $\textit{KK-MBF}$ functions the time complexity of Hansel algorithm remains $\sim {C_{n}^{[n/2]}}$ so $O({n^{2}})$ is a valuable reduction of the complexity characteristics. But the techniques of Tonoyan (1979) and Sokolov (1987) for the reduction of memory used in Hansel algorithm can not be applied in the case of our layer bisection approach.
To find a way to reduce the memory complexity we continue to address algorithmic questions on layers from an additional perspective. In order to apply bisections on layers, we need to keep all ${2^{n}}$ vertices (ordered lexicographically, layer-by-layer) in computer memory. Otherwise, we need to find a vertex by its number in lexicographic order, or by a distance from a certain vertex (again, in lexicographic order). There are no explicit formulas for this. Thus, both cases will require appropriate time and memory resource.
One way to avoid this situation is using sub-cube structures on layers when partitioning the cube. This is easily applicable to find the 0–1 border on layers, although it will require more than logarithmic queries on layers.
We will use ${\alpha _{j}^{k}}$ for the j-th element of ${L_{k}}$ in the lexicographic order. Then the smallest element of ${L_{k}}$ in the lexicographic order is ${\alpha _{1}^{k}}=(\stackrel{k}{\overbrace{11\dots 1}}\stackrel{n-k}{\overbrace{00\dots 0}})$, and the largest one is the element ${\alpha _{{C_{n}^{k}}}^{k}}=$ ($\stackrel{n-k}{\overbrace{00\dots 0}}\stackrel{k}{\overbrace{11\dots 1})}$.
Let ${B_{{x_{1}}=1}^{n-1}}$ and ${B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}$ be the partitions of ${B^{n}}$ according to ${x_{1}}$, and ${L_{{k,x_{1}}=1}}$ and ${L_{{k,x_{1}}=0}}$ denote the parts of ${L_{k}}$ in ${B_{{x_{1}}=1}^{n-1}}$ and ${B_{{x_{1}}=\hspace{0.1667em}0}^{n-1}}$, respectively. Then ${\alpha _{1}}=\stackrel{k}{(0\overbrace{11\dots 1}}\stackrel{n-k-1}{\overbrace{00\dots 0}})$ is the lexicographically smallest element of ${L_{k,{x_{1}}=\hspace{0.1667em}0}}$, and ${\alpha _{0}}=(1\stackrel{n-k}{\overbrace{00\dots 0}}\stackrel{k-1}{\overbrace{11\dots 1}})$ is the lexicographically largest element of ${L_{{k,x_{1}}=1}}$.
Instead of taking the arithmetical middle vertex of ${L_{k}}$ to ask/test the function value, we take either ${\alpha _{1}}$ or ${\alpha _{0}}$ (for certainty, we will take ${\alpha _{1}}$). If $f({\alpha _{1}})=1$, then $f(\alpha )=1$ for all $\alpha \in {L_{{k,x_{1}}=1}}$; therefore, the next vertex that we will take to ask the function value is the largest element of ${L_{k,{x_{1}}=\hspace{0.1667em}0,{x_{2}}=\hspace{0.1667em}0}}$ (the part of ${L_{k}}$ in ${B_{{x_{1}}=\hspace{0.1667em}0,{x_{2}}=\hspace{0.1667em}0}^{n-2}}$), this is element ${\alpha _{2}}=\stackrel{k}{(00\overbrace{11\dots 1}}\stackrel{n-k-2}{\overbrace{00\dots 0}})$.
If $f({\alpha _{1}})=0$, then $f(\alpha )=0$ for all $\alpha \in {L_{{k,x_{1}}=\hspace{0.1667em}0}}$; therefore, the next vertex that we will take is the largest element of ${L_{k,{x_{1}}=1,{x_{2}}=\hspace{0.1667em}0}}$ (the part of ${L_{k}}$ in ${B_{{x_{1}}=1,{x_{2}}=\hspace{0.1667em}0}^{n-2}}$), this is the element ${\alpha _{2}}=\stackrel{k-1}{(10\overbrace{11\dots 1}}\stackrel{n-k-1}{\overbrace{00\dots 0})}$.
In general, in ${B_{{x_{1}}=\hspace{0.1667em}{\sigma _{1}},\dots ,{x_{i}}={\sigma _{i}}}^{n-i}}$ the largest element of k-th layer is
${\sigma _{1}}\dots {\sigma _{i}}\stackrel{x}{\overbrace{11\dots 1}}\stackrel{y}{\overbrace{00\dots 0}}$, where x is k minus the number of 1s in ${\sigma _{1}}\dots {\sigma _{i}}$, and y is $(n-k)$ minus the number of 0s in ${\sigma _{1}}\dots {\sigma _{i}}$.
In this way, after each query, we continue in a smaller sub-cube, and hence, the number of queries in each layer can be at most $n-1$. For the heaviest layer, for $k=n/2$, we get the same estimate, but without either keeping all vertices in computer memory or calculating the given j-th vertex in the lexicographic order. Indeed, the number of vertices of middle layer equals ${C_{n}^{[n/2]}}\sim \frac{{2^{n+1}}}{\sqrt{2\pi n}}$ when $n\to \infty $. Logarithm of this, the number of steps in dichotomy, is equivalent to $n-1$, and so the partition by cube structures is simple and effective.
Proposition 5.
Reconstruction of monotone Boolean functions of class $\textit{KK-MBF}$ can be organized with complexity $O({n^{2}})$ without keeping the cube structure in computer memory.
As an example, consider the function given in Fig. 4, and suppose that $k=3$. Then,
${\alpha _{1}}=(01110)$, and since $f(01110)=0$, the next vertex is
${\alpha _{2}}=(10110)$. $f(10110)=1$, and it follows that the next is
${\alpha _{3}}=(10011)$. $f(10011)=1$.
This way, we found the corner points $f(01110)=0$ and $f(10011)=1$ of the third layer.
So far, when recognizing $\textit{KK-MBF}$ functions layer by layer, we have only used the fact that the function satisfies the condition Cond-h and have not used the monotonicity of the function. Using the monotonicity will narrow the space for taking the next vertex for testing.
Suppose that ${\alpha _{k}}$ is the smallest vertex of ${L_{k}}$ in the lexicographic order with $f({\alpha _{k}})=1$. Denote by ${\alpha _{k+1}}$ the lexicographically smallest upper neighbour of ${\alpha _{k}}$ in ${L_{k+1}}$. Then, at the next step, we need to consider only those vertices of ${L_{k+1}}$, lexicographically smaller than ${\alpha _{k+1}}$.
For the given example in Fig. 4, $(10100)$ is the smallest vertex of ${L_{2}}$ in the reverse-lexicographic order, where the function value is 1. Then, we will choose the next vertex in the interval $[(00111),(10011)]$ instead of $[(00111),(11100)]$.
But to calculate the length of the interval $[\text{reverse-lexicographically first vertex of}\hspace{2.5pt}{L_{k+1}}$, ${\alpha _{k+1}}]$ we need to find the number of ${\alpha _{k+1}}$ in lexicographic order. Effective solution of this problem is still open.
Here as well, one can use sub-cube structures, but the benefit is only in the case when ${f(\alpha _{k+1}})=0$.
We conclude the section with the following general note. It addresses an alternative partial order of vertices to the traditional monotony based order, where $\alpha \preccurlyeq \beta $ if α coordinate-wise precedes β. In terms of $\textit{KK-MBF}$, each of the vertices α and β creates 2 domains: upper domains $\hat{d}(f,\alpha )$ and $\hat{d}(f,\beta )$, when $f(\alpha )=f(\beta )=1$, and lower domains $\check{d}(f,\alpha )$ and $\check{d}(f,\beta )$, when $f(\alpha )=f(\beta )=0$. In this case we define the following order: $\alpha {\preccurlyeq _{d}}\beta $ if $d(f,\alpha )\subseteq d(f,\beta )$ with $f(\alpha )=f(\beta )=0$, and, which is the same, $\alpha {\preccurlyeq _{d}}\beta $ if $d(f,\alpha )\supseteq d(f,\beta )$ with $f(\alpha )=f(\beta )=1$. Otherwise, vertices α and β are incomparable. We call this construction KK-poset. Sperner type family may be obtained as a simple extension of this concept to the case of KK-poset. Here, similar to general MBFs, each $\textit{KK-MBF}$ is given by two complementary Sperner families – one is composed by 0-corner points, and the other includes all maximal 1-corner points of the function. We obtain that the $\textit{KK-MBF}$ reconstruction is similar to the MBF reconstruction, just the basic space and poset is a bit different. The technique developed for the general MBF and the experiences may be used in the problem of reconstruction of $\textit{KK-MBF}$ functions. We consider this reduction and transfer from MBF to $\textit{KK-MBF}$ an interesting research topic that is worthy of further investigations.
4 Cardinality of KK-MBF Class
Another important issue is the size of the whole class of $\textit{KK-MBF}$ functions (Korshunov, 2003; BFA, 2023; Jung, 2023). First, let us note that the function, given through ${p_{n/2}}={C_{n}^{n/2}}$ (with all other layer characteristics equal to 0), belongs to the class $\textit{KK-MBF}$ and is the only function with the largest number of lower units. Therefore, to count the number of $\textit{KK-MBF}$ functions, we need to consider the number of non-negative integer partitions for an arbitrary positive integer $p,1\leqslant p\leqslant {C_{n}^{n/2}}$: $p={p_{1}}+{p_{2}}+\cdots +{p_{n-1}}$ (excluding the boundary cases $p={p_{0}}=1$ and $p={p_{n}}=1$), such that ${0\leqslant p_{1}}\leqslant |[{\alpha _{1}^{s}},{\alpha _{1}^{l}}]|$, ${0\leqslant p_{2}}\leqslant |[{\alpha _{2}^{s}},{\alpha _{2}^{l}}]|,\dots ,{0\leqslant p_{n-1}}\leqslant |[{\alpha _{n-1}^{s}},{\alpha _{n-1}^{l}}]|$, where $[{\alpha _{j}^{s}},{\alpha _{j}^{l}}]$ is the feasible interval of vertices on the j-th layer with ${\alpha _{j}^{s}}$ as the smallest and ${\alpha _{j}^{l}}$ as the largest element in the lexicographic order. These smallest and largest elements are defined in the following way. For all intervals, ${\alpha _{j}^{s}}$ is the lexicographically smallest element of the j-th layer. As for the largest elements, – ${\alpha _{1}^{l}}$ is the largest element of the first layer. To find ${\alpha _{2}^{l}}$, we consider the smallest element of ${\delta ^{1+1}}{\mathcal{M}_{1}}$, where ${\mathcal{M}_{1}}$ is the final ${m_{1}}$ element on the 1st layer in the lexicographic order, and ${\alpha _{2}^{l}}$ is the vertex previous to it. To find ${\alpha _{3}^{l}}$, we consider the smallest element of ${\delta ^{2+1}}{\mathcal{M}_{2}}$, where ${\mathcal{M}_{2}}$ is the next ${m_{2}}$ elements on the 2nd layer in the lexicographic order, after ${\delta ^{1+1}}{\mathcal{M}_{1}}$, and ${\alpha _{3}^{l}}$ is the vertex previous to it.
In general, ${\alpha _{j}^{l}}$ is the previous to the smallest element of ${\delta ^{j}}{\mathcal{M}_{j-1}}$ in the lexicographic order, where ${\mathcal{M}_{j-1}}$ is the next ${p_{j-1}}$ element of the $(j-1)$-th layer after ${\delta ^{j-1}}{\mathcal{M}_{j-2}}$.
Note that among ${p_{1}},{p_{2}},\dots ,{p_{n-1}}$ at most $n-2$ elements can be positive. Moreover, all $n-2$ elements can be positive only in restricted cases, i.e. when ${p_{1}}={p_{2}}=\cdots ={p_{n-2}}=1$.
Thus, constraints on ${p_{i}}$ are imposed not only in the form of ${0\leqslant p_{i}}\leqslant |[{\alpha _{i}^{s}},{\alpha _{i}^{l}}]|$, but also on their numbers depending on the previous values of ${p_{1}},{p_{2}},\dots ,{p_{i-1}}$. This is one way of counting the number of elements of the class, but it is not easy to obtain an explicit formula in this manner.
Let C denote a particular subclass of $\textit{KK-MBF}$ functions having one 0-corner point at any layer of the cube.
To construct this subclass we take an arbitrary point $\alpha \in {B^{n}}$ and define the function by 0 value in the point α and in the domain $d(f,\alpha )$. f may have one or several 1-corner points. Since we may choose the point α in ${2^{n}}$ different ways, we get that $|C|\geqslant {2^{n}}$.
5 Special Cases
In this section, we address another particular subclass of $\textit{KK-MBF}$ functions, which is related to the cascades of Kruskal.
Let ${R_{t}}(n)$ denote the initial t-length segment of the reverse lexicographic ordering on ${B^{n}}$. ${R_{t}}(n)$ corresponds to the set of units of a monotone Boolean function, denote it by ${f_{R}}$, the structure of which can be illustrated as in Fig. 5, where ${k_{1}},{k_{2}},\dots ,{k_{p}}$ are parameters in binary representation of t, $t={2^{{k_{1}}}}+{2^{{k_{2}}}}+\cdots +{2^{{k_{p}}}}$; ${k_{1}}\gt {k_{2}}\gt \cdots \gt {k_{p}}\gt 0$.
Let $S=({s_{1}},{s_{2}},\dots ,{s_{n}})$ be the associated vector of partitions of ${R_{t}}(n)$, composed as ${s_{i}}=|{{R_{t}}(n)_{{x_{i}}=1}}|$, $i=1,\dots ,n$.
It is known (Sahakyan, 2013, 2015) that ${f_{R}}$ is the unique monotone Boolean function (up to variable permutations) with the smallest sum of coordinates of its associated vector of partitions among all monotone Boolean functions with t units. The coordinates of $S=({s_{1}},\dots ,{s_{n}})$ are also calculated.
Numbers of lower units of ${f_{R}}$ on the layers $n-{k_{1}},n-{k_{2}}-1,\dots ,n-{k_{p}}-1$ are determined by t.
Equivalently, ${f_{R}}$ can be constructed in the following way:
Consider again the binary representation of t:
Suppose that the first positive summand is ${2^{{k_{1}}}}$ (${\alpha _{{k_{1}}}}=1)$. We construct an interval with the lower unit as the smallest vertex of the ${n-k_{1}}$-th layer by the reverse lexicographic order. If the next ${\alpha _{{k_{1}}-1}}\gt 0$, then we take the next vertex of the reverse lexicographic order as a lower unit, and compose an interval. If a current ${\alpha _{{k_{1}}-j}}=0$, then we go up (we go up as many times as they are 0), and take the smallest vertex of the reverse lexicographic order (which is not in the upper shadows of the constructed intervals).
By constructing the same function in this manner, we know the numbers of lower units in layers, depending on t.
Thus, for a given t, we constructed a $\textit{KK-MBF}$ function with t units, and we also know its characteristics, $\mathrm{\# }\min T({f_{R}})=\langle {p_{{i_{1}}}},{p_{{i_{2}}}},\dots ,{p_{{i_{r}}}}\rangle $.
On the other hand, if given characteristics $\mathrm{\# }\min T({f_{R}})=\langle {p_{{i_{1}}}},{p_{{i_{2}}}},\dots ,{p_{{i_{r}}}}\rangle $ of some $\textit{KK-MBF}$ function, we can count the number of its units.
In general, it is possible to impose restrictions on the numbers/layers of the lower units of $\textit{KK-MBF}$ functions to get this special subclass.
6 Concluding Remarks
Boolean functions are not only a means of computing functional dependencies, but also represent a suitable mathematical apparatus for modelling data science systems. The limitations of models and the structure of their joint collections are reduced to considering Boolean functions that have the property of monotonicity. However, decoding monotone Boolean functions is a multifaceted problem, and there remain many unsolved or inefficiently solved problems in this context. Combinatorial constructions have been considered in some detail, but they are complex and often reduced to enumeration (brute-force). A possible new approach is to bring in a new resource, namely that of artificial intelligence (Valiant, 1984; Sahakyan et al., 2022; Zhuravlev et al., 2019, 2020). In this formulation, the emphasis is placed on solving a large number of problems of the class under consideration, accumulating the results of solutions in the form of a database, training on them, and not solving but recognizing the solution of the problem under consideration by analysing the parameters of the problem and the database information. The problem in this formulation is already becoming popular, and our first results related to it refer to decoding arbitrary monotone Boolean functions and are presented in Sahakyan et al. (2022).
Another possible approach continues the first one and seeks ways of refining, and reconstructing the problem constraints, with subtypes of monotone Boolean functions appearing, the decoding of which requires refined approaches, and the associated algorithms, whether combinatorial or based on machine learning, that can be practically implemented. There is a list of practical problems in big data analytics that reduce to the diverse classes of monotone Boolean functions. We begin the study of one of the classes of such functions – shadow minimized Boolean functions, for subsets of finite sets. We proceeded from the well-known solution of the problem for layers, formulated in the form of the Kruskal-Katona theorem, and on the extension of this fact to all layers of the cube, when the existence conditions for Sperner systems are obtained. We were able to show that the class of these functions has the structure of a generating set, which is not a necessary property of arbitrary classes of functions. Basic structures of data analysis of the problem of identification of these functions, details of memory organization in the optimal mode are also given, but we consider the beginning of these investigations as the main step, and we think that subsequent investigations will give acceptable complexity results for solving these problems, both in this and in other systems of functions with constraints.
