UDC 519.95

CYBERNETICS AND CONTROL THEORY

L. S. KHASIN

ESTIMATES OF THE COMPLEXITY OF REALIZING MONOTONE SYMMETRIC FUNCTIONS BY FORMULAS IN THE BASIS \(\vee, \&, \neg\)

(Presented by Academician L. V. Kantorovich, January 28, 1969)

A monotone symmetric function of the algebra of logic with threshold \(p\) is the function \(f_p(x_1,\ldots,x_n)\) defined by the formula

\[ f_p(x_1,\ldots,x_n)= \bigvee_{1\le i_1<i_2<\cdots<i_p\le n}. \]

Let \(L_{\Pi}(\sigma_n)\) be the smallest number of letters sufficient for realizing any symmetric function of \(n\) arguments by a formula, and let \(L_p(n)\) be the smallest number of letters sufficient for realizing, by a formula, \(f_p(x_1,\ldots,x_n)\).

This note is devoted to finding upper estimates for \(L_p(n)\). The best upper estimate for \(L_{\Pi}(\sigma_n)\) is the estimate obtained by O. B. Lupanov \((^1)\):

\[ L_{\Pi}(\sigma_n)\preccurlyeq n^{\log_2\log_2 n(1+\delta_n)},\quad \text{where } \delta_n\to 0,\ n\to\infty. \]

If \(p\) is fixed, then the best upper estimate for \(L_p(n)\) is the estimate obtained by the author \((^2)\):

\[ L_p(n)\preccurlyeq n\frac{(\log_2 p)^{p-1}}{(\log_2\log_2 n)^{p-2}}\ * , \]

and the best lower estimate is the estimate obtained by R. E. Krichevskii \((^3)\)

\[ L_2(n)\succcurlyeq n\log_2 n. \tag{1} \]

By a formula of depth 3 we shall mean a disjunction of conjunctions of disjunctions of variables.

In the present note the following results are obtained:

1. For fixed \(p\), \(L_p(n)\asymp n\log_2 n\), and the estimate is attained even on formulas of depth 3. More precisely, the following inequality holds:

2. \[ L_p^3(n)\preccurlyeq n\log_2 n\cdot e^{p(1+\alpha_p)}, \]
   where \(\alpha_p\to 0,\ p\to\infty\), and \(L_p^3(n)\) is the complexity of a minimal formula of depth 3 realizing \(f_p(x_1,\ldots,x_n)\).

3. \[ L_p(n)\preccurlyeq 2^{1/4(\log_2 p)^2(1+\beta_p)}\,n\log_2 n, \]
   where \(\beta_p\to 0,\ p\to\infty\).

4. \[ L(n,p)\preccurlyeq 2^{1/4(\log_2 p)^2(1+\gamma_p)}\,n\log_2 n, \]
   where \(\gamma_p\to 0,\ p\to\infty\), and \(L(n,p)\) is the smallest number of letters sufficient for realizing, by a formula in the basis \(\vee, \&, \neg\), a symmetric function whose working numbers lie between \(0\) and \(p\). It should be noted that all estimates are obtained ineffectively, i.e., the formulas on which these estimates are attained are not constructed.

Theorem 1. For \(L_p(n)\) the inequality

\[ L_p(n)\preccurlyeq 2^{1/4(\log_2 p)^2(1+\beta_p)} \,n\log_2 n,\quad \text{where } \beta_p\to 0,\ p\to\infty, \]

holds.

* In this note the following notation is used: \(a(m)\preccurlyeq b(m)\) means that there exist constants \(c_1\) and \(c_2\) such that for \(m>c_1\) the inequality \(a(m)\le c_2 b(m)\) holds; \(a(m)\succcurlyeq b(m)\), \(-b(m)\preccurlyeq a(m)\); \(a(m)\asymp b(m)\), \(-a(m)\preccurlyeq b(m)\) and \(a(m)\succcurlyeq b(m)\).

Proof. Let first \(n=2^m,\ p=2^k\) \((1\le k\le m)\). Define the class of formulas \(M(n,l_0,l_1,\ldots,l_{k-1})\) and choose the parameters \(l_0,\ldots,l_{k-1}\) so that in this class there exists a formula realizing \(j_p(x_1,\ldots,x_n)\). Consider a tree \(S\) with root (4). Let the number of levels of the tree be \(2k+2\), and let the number of arcs issuing from an arbitrary vertex of the \(i\)-th level be equal to 2 if \(i\) is odd and \(i\ne 2k+1\), equal to \(n/p\) if \(i=2k\), and equal to \(l_j\) if \(i=2j\) \((0\le j\le k-1)\). To each path issuing from a vertex of the \(i\)-th level we assign the symbol \(\vee\), if \(i\) is odd, and \(\&\), if \(i\) is even and \(i\ne 2k\). To the root we assign the symbol \(\vee\). For example, Fig. 1 shows the tree for \(n=2^1\) and \(p=2^1,\ l_0=2\). Let \(\mathfrak N=\{x_1,\ldots,x_n\}\) be the set of \(n\) binary variables. Put \(n_j=n/2^j\) \((0\le j\le k)\). To each terminal vertex we assign a variable from \(\mathfrak N\) in such a way that condition A is satisfied.

Condition A. Let \(a\) be an arbitrary vertex of the \((2j-1)\)-st level, \(1\le j\le k\). Then the sets of variables assigned to the terminal vertices of the subtrees generated by the vertices \(a_1\) and \(a_2\) of the \(2j\)-th level following \(a\) must not intersect, and each of them must contain \(n_j\) elements.

Let variables be assigned in some way to the terminal vertices of \(S\) so that condition A is satisfied. Consider the subtree \(S(a)\) generated by the vertex \(a\) of the \(2i\)-th level. To this subtree one can uniquely associate a formula. This formula realizes a function equal to the disjunction of some conjunctions of length \(p_i=p/2^i\) in the \(n_i\) variables assigned to the terminal vertices of the subtree \(S(a)\). Thus, for example, the tree in Fig. 1 corresponds to the formula

Fig. 1

\[ F(x_1,\ldots,x_4)=x_1x_2\vee x_1x_3\vee x_1x_4\vee x_2x_3\vee x_2x_4\vee x_3x_4. \]

We shall regard two formulas corresponding to the subtree \(S(a)\) as identical if and only if, for an arbitrary vertex of the \(2k\)-th level belonging to \(S(a)\), the sets of variables assigned to the terminal vertices of the subtree generated by it coincide.

Denote by \(M(n_i,l_i,\ldots,l_{k-1})\) the set of all formulas corresponding to the subtree \(S(a)\) generated by a vertex \(a\) of the \(2i\)-th level, and the number of elements of this set by \(|M(n_i,l_i,\ldots,l_{k-1})|\). Then

\[ |M(n_i,l_i,\ldots,l_{k-1})| =\left(C_{n_i}^{\,n_i/2}\,|M(n_{i+1},l_{i+1},\ldots,l_{k-1})|^2\right)^{l_i}, \]

\[ i=0,\ldots,k-2, \tag{2} \]

\[ |M(n_{k-1},l_{k-1})| =\left(C_{n_{k-1}}^{\,n_k/2}\right)^{l_{k-1}}. \]

Let

\[ C_{n_i}^{\,n_i/2}\,|M(n_{i+1},l_{i+1},\ldots,l_{k-1})|^2 =R(n_{i+1},l_{i+1},\ldots,l_{k-1}). \]

Then

\[ |M(n_i,l_i,l_{i+1},\ldots,l_{k-1})| =\left(R(n_{i+1},l_{i+1},\ldots,l_{k-1})\right)^{l_i}. \tag{3} \]

We shall say that \(F\in M(n_i,l_i,\ldots,l_{k-1})\) does not generate the conjunction
\(x_{t_1}\cdots x_{t_l}\) (the \(x_{t_j}\) are taken from the set of variables on which \(F\) depends) if the reduced disjunctive normal form of the function realized by \(F\) does not contain this conjunction. Clearly, the number of formulas not generating a concrete conjunction is the same for all conjunctions. Let
\(|\overline M(n_i,l_i,\ldots,l_{k-1})|\) be the number of such formulas for any conjunction. Then

\[ |\overline M(n_i,l_i,\ldots,l_{k-1})| =\left(\overline R(n_{i+1},l_{i+1},\ldots,l_{k-1})\right)^{l_i}, \]

where

\[ \overline{R}(n_{i+1}, l_{i+1}, \ldots, l_{k-1}) = R(n_{i+1}, l_{i+1}, \ldots, l_{k-1}) - \]

\[ -\, C_{p_i}^{p_i/2} C_{n_i-p_i}^{\,n_i/2-p_i/2} \left( |M(n_{i+1}, l_{i+1}, \ldots, l_{k-1})| - |\overline{M}(n_{i+1}, l_{i+1}, \ldots, l_{k-1})| \right)^2, \tag{4} \]

\[ i=0,\ldots,k-2; \]

\[ |\overline{M}(n_{k-1}, l_{k-1})| = \left(C_{n_{k-1}}^{\,n_{k-1}/2} - 2C_{n_{k-1}-2}^{\,n_{k-1}/2-1} \right)^{l_{k-1}}. \]

Put

\[ \frac{|\overline{M}(n_i, l_i,\ldots,l_{k-1})|} {|M(n_i, l_i,\ldots,l_{k-1})|} = a_i, \qquad i=0,\ldots,k-1. \]

Then, taking into account (2), (3), (4), we have

\[ a_i = \left( 1- \frac{C_{p_i}^{p_i/2} C_{n_i-p_i}^{\,n_i/2-p_i/2}} {C_{n_i}^{\,n_i/2}} (1-a_{i+1})^2 \right)^{l_i}, \qquad i=0,\ldots,k-2. \]

\[ a_{k-1} = \left( 1- 2\frac{C_{n_{k-1}-2}^{\,n_{k-1}/2-1}} {C_{n_{k-1}}^{\,n_{k-1}/2}} \right)^{l_{k-1}}. \tag{5} \]

It is not difficult to verify that if \(l_0,\ldots,l_{k-1}\) are chosen from the condition \(a_0 < 1/C_n^p\), then in the class \(M(n,l_0,\ldots,l_{k-1})\) there is a formula realizing the function equal to the disjunction of all conjunctions of length \(p\) in the variables \(x_1,\ldots,x_n\), i.e. \(f_p(x_1,\ldots,x_n)\). Choose \(l_0,\ldots,l_{k-1}\) successively from the condition

\[ a_i \leqslant \frac12,\ i=1,\ldots,k-1, \qquad a_0 < 1/C_n^p. \tag{6} \]

Since

\[ 1-2C_{n_{k-1}-2}^{\,n_{k-1}/2-1}/C_{n_{k-1}}^{\,n_{k-1}/2} \leqslant \frac12, \]

then for \(l_{k-1}=1\) condition (6) is fulfilled for \(i=k-1\). Suppose \(l_{i+1},\ldots,l_{k-1}\) have already been chosen so that condition (6) is fulfilled for

\[ a_{i+1},\ldots,a_{k-1} \qquad (1\leqslant i\leqslant k-2). \]

Then the inequality is valid

\[ 1- \frac{C_{p_i}^{p_i/2} C_{n_i-p_i}^{\,n_i/2-p_i/2}} {C_{n_i}^{\,n_i/2}} (1-a_{i+1})^2 \leqslant 1- \frac14 \frac{C_{p_i}^{p_i/2} C_{n_i-p_i}^{\,n_i/2-p_i/2}} {C_{n_i}^{\,n_i/2}} \leqslant \]

\[ \leqslant \{\text{using the refinement of Stirling’s formula (5)}\} \leqslant \]

\[ \leqslant 1-\frac14 \frac{\sqrt{2/\pi}\,2^{p_i}\sqrt{2/\pi}\,2^{\,n_i-p_i}\sqrt{n_i}} {i^{1/3}\sqrt{p_i}\sqrt{n_i-p_i}\sqrt{2/\pi}\,2^{n_i}} \leqslant 1-\frac{1}{c} \frac{1}{\sqrt{1-p/n}\sqrt{p_i}}. \tag{7} \]

Choose \(l_i\) from the condition

\[ l_i>8\sqrt{1-p/n}\sqrt{p_i}; \tag{8} \]

Then

\[ a_i \leqslant \{\text{taking into account (7), (8)}\} \leqslant \left( 1-\frac{1}{8\sqrt{1-p/n}\sqrt{p_i}} \right)^{8\sqrt{1-p/n}\sqrt{p_i}} \leqslant \]

\[ \leqslant \{\text{since } \log_2(1-x)\leqslant -x,\ 0\leqslant x<1\} \leqslant \frac12. \]

Thus, if \(l_i\) \((1\leqslant i\leqslant k-2)\) are chosen in accordance with (8), and \(l_{k-1}\) is set equal to 1, then (6) will be fulfilled for \(i=1,\ldots,k-1\). Let \(l_1,\ldots,l_{k-1}\) be chosen in the indicated way. Choose \(l_0\) from the condition:

\[ l_0>8\sqrt{1-p/n}\,p^{3/2}\log_2 n. \tag{9} \]

Then, taking into account that (7) is now also valid for \(i=0\), and also the inequality \(\log_2 C_n^p < p\log_2 n\), we have

\[ a_0<1/C_n^p. \]

Let \(l_0,\ldots,l_{k-1}\) be chosen according to (8), (9), and let \(l_{k-1}=1\). Then there exists a formula \(F \in M(n,l_0,\ldots,l_{k-1})\) that realizes \(f_p(x_1,\ldots,x_n)\). The complexity of this formula satisfies the inequality

\[ L_F(n) \leq \frac{n}{p}\,2l_0\,2l_1\cdots 2l_{k-1} = nl_0\cdots l_{k-1}, \]

i.e., there exists a formula whose complexity satisfies the inequality

\[ L_F(n) \leq n \prod_{i=1}^{k-1} \left(8\sqrt{1-p/n}\sqrt{p_i}+1\right) \left(8\sqrt{1-p/n}\,p^{3/2}\log_2 n+1\right) \leq 2^{\frac14(\log_2 p)^2(1+\tau_p)}\,n\log_2 n, \]

where \(\tau_p \to 0\) as \(p \to \infty\).

Thus, we have

\[ L_p(n) \leq 2^{\frac14(\log_2 p)^2(1+\tau_p)}\,n\log_2 n, \tag{10} \]

where \(\tau_p \to 0,\ p\to\infty\) \((n=2^m,\ p=2^k,\ 1\leq k\leq m-1)\).

For \(p=n=2^m\), inequality (10), obviously, is also valid. Let \(n\) and \(p\) be arbitrary. Then the validity of the asserted theorem is established with the aid of (10) and the relations

\[ f_p(x_1,\ldots,x_n) = f_q(x_1,\ldots,x_n, \underbrace{1,\ldots,1}_{q-p}), \]

\[ f_q(x_1,\ldots,x_{n+q-p}) = f_q(x_1,\ldots,x_{n+q-p}, \underbrace{0,\ldots,0}_{N-(n+q-p)}). \tag{11} \]

Theorem 1 is proved.

Theorem 2. The inequality

\[ L_p^3(n) \leq l^p{}^{(1+\alpha_p)}\, n\log_2 n, \qquad \text{where } \alpha_p\to 0,\ p\to\infty, \]

is valid.

The proof is analogous to the proof of Theorem 1.

Corollary 1. For fixed \(p\),

\[ L_p(n) \asymp n\log_2 n. \]

The proof is easily obtained using Theorem 2 and relations (1) and (11).

Corollary 2.

\[ L(n,p) \leq 2^{\frac14(\log_2 p)^2(1+\gamma_p)}\,n\log_2 n, \qquad \gamma_p\to 0,\ p\to\infty. \]

The proof follows from Theorem 1 and the relation

\[ \varphi_p(x_1,\ldots,x_n) = f_p(x_1,\ldots,x_n)f_{p+1}(\bar{x}_1,\ldots,\bar{x}_n), \]

where \(\varphi_p(x_1,\ldots,x_n)\) is the elementary symmetric function with working number \(p\).

The author takes this opportunity to express deep gratitude to V. K. Leont’ev for valuable comments.

Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR
Novosibirsk

Received
29 XII 1968

References

1. O. B. Lupanov, in: Problems of Cybernetics, vol. 15, “Nauka,” 1965, p. 85.
2. L. S. Khasin, in: Problems of Cybernetics, vol. 24, “Nauka,” 1969.
3. R. E. Krichevskii, in: Discrete Analysis, vol. 1, 1963, p. 13.
4. K. Berge, Theory of Graphs and Its Applications, IL, 1962.
5. W. Feller, An Introduction to Probability Theory and Its Applications, Moscow, 1967, p. 67.