UDC 519.95

MATHEMATICS

G. P. KAREV, S. A. TRESKOV, G. Sh. FRIDMAN

ESTIMATING THE COMPLEXITY OF A FUNCTION OF THE ALGEBRA OF LOGIC

(Presented by Academician M. A. Lavrentiev, 13 IV 1965)

Let an arbitrary finite set \(M\) be given, consisting of elements \(A_1,\ldots,A_k\). Consider the set \(S(M)\) of all subsets of the set \(M\). Let also a predicate \(P(\mathfrak{M})\) be specified, defined on the elements \(\mathfrak{M}\) of the aggregate \(S(M)\).

Example. As \(M\) one may consider an aggregate of sets \(M_1,\ldots,M_k\), and define the predicate \(P(\mathfrak{M})\) in the following way: let \(\hat M \subseteq \bigcup_{i=1}^{k} M_i\) and \(\mathfrak{M}=\{M_{i_1},\ldots,M_{i_t}\}\). Then

\[ P(\mathfrak{M})= \begin{cases} 1, & \text{if } \hat M \subseteq \displaystyle\bigcup_{j=1}^{t} M_{i_j},\\[6pt] 0, & \text{if } \hat M \nsubseteq \displaystyle\bigcup_{j=1}^{t} M_{i_j}. \end{cases} \]

Associate with the element \(A_i,\ i=1,2,\ldots,k\), of the set \(M\) a variable \(y_i,\ y_i\in\{0,1\}\), and introduce the following function of the algebra of logic.

Let \((\alpha_1,\ldots,\alpha_k)\) be an arbitrary vertex of the \(k\)-dimensional unit cube, \(\alpha_{i_1}=\alpha_{i_2}=\cdots=\alpha_{i_q}=1\), and let the remaining coordinates be equal to zero. Associate with the vertex \((\alpha_1,\ldots,\alpha_k)\) the subset \(\mathfrak{M}=\{A_{i_1},\ldots,A_{i_q}\}\). Then:

\[ f(\alpha_1,\ldots,\alpha_k)= \begin{cases} 1, & \text{if } P(\mathfrak{M})=1,\\ 0, & \text{if } P(\mathfrak{M})=0. \end{cases} \tag{1} \]

The introduced function \(f(y_1,\ldots,y_k)\) is “characteristic” for the property \(P(\mathfrak{M})\). Therefore the complexity of realizing \(f\) in some basis characterizes the laboriousness of computing \(P(\mathfrak{M})\).

As the set \(M\) we shall consider the aggregate of all elementary conjunctions of the variables \(x_1,\ldots,x_n\). Then \(S(M)\) is the aggregate of all subsets of elementary conjunctions. Introduce the predicate \(P(\mathfrak{M})\), \(\mathfrak{M}=\{A_{i_1},\ldots,A_{i_k}\}\):

\[ P(\mathfrak{M})= \begin{cases} 1, & \text{if } \displaystyle\bigvee_{j=1}^{k} A_{i_j} \text{ is the reduced d.n.f. of some}\\ & \text{function of the algebra of logic in the variables } x_1,\ldots,x_n,\\[6pt] 0 & \text{otherwise.} \end{cases} \]

The function \(f(y_1,\ldots,y_k)\) is introduced according to (1). Obviously, the number of variables of the function \(f\) is equal to the number of distinct elementary conjunctions in the variables \(x_1,\ldots,x_n\), i.e. is equal to \(3^n\).

We shall estimate the complexity of the shortest d.n.f. for the function \(f(y_1,\ldots,y_k)\). Introduce definitions needed in what follows. Let \(\tilde{\alpha}=(\alpha_1,\ldots,\alpha_n)\), \(\tilde{\beta}=(\beta_1,\ldots,\beta_n)\).

Definition 1. The Hamming distance \(\rho(\tilde{\alpha},\tilde{\beta})\) is the quantity
\[ \sum_{i=1}^{n}|\alpha_i-\beta_i|. \]

Definition 2. A ball with center \((\alpha_1,\ldots,\alpha_n)\) is the set of points whose distance from \((\alpha_1,\ldots,\alpha_n)\) is not greater than 1.

Definition 3. \(\tilde{\alpha}=(\alpha_1,\ldots,\alpha_n)\geqslant \tilde{\beta}=(\beta_1,\ldots,\beta_n)\), if \(\alpha_i\geqslant\beta_i,\ i=1,\ldots,n\).

Definition 4. A point \(\tilde{\alpha}=(\alpha_1,\ldots,\alpha_n)\) is an upper neighbor for \(\tilde{\beta}=(\beta_1,\ldots,\beta_n)\), if \(\rho(\alpha,\beta)=1\) and \(\alpha\geqslant\beta\).

Let \(\varphi(x_1,\ldots,x_n)\) be an arbitrary function of the algebra of logic.

Definition 5. A vertex \((\alpha_1,\ldots,\alpha_n)\) is called an upper point of the function \(\varphi(x_1,\ldots,x_n)\), if \(\varphi(\alpha_1,\ldots,\alpha_n)=1\) and all upper neighboring vertices for \((\alpha_1,\ldots,\alpha_n)\) do not belong to \(N_\varphi\).

Let \(\mathfrak{A}=x_{i_1}^{\sigma_1}\cdots x_{i_k}^{\sigma_k}\) and let \(N_{\mathfrak{A}}\) be the interval corresponding to the conjunction \(\mathfrak{A}\).

Definition 6. A vertex \((\alpha_1,\ldots,\alpha_n)\) of \(N_{\mathfrak{A}}\) is called the pole of the interval \(N_{\mathfrak{A}}\) (notation \(\tilde{\alpha}(\mathfrak{A})\)), if \(\alpha_{i_1}=\sigma_1,\ldots,\alpha_{i_k}=\sigma_k\) and all remaining coordinates are equal to 1.

Remark 1. If \(\tilde{\beta}\in N_{\mathfrak{A}}\), then \(\tilde{\beta}\leqslant\tilde{\alpha}(\mathfrak{A})\).

Remark 2. If \(\tilde{\beta}\in N_{\mathfrak{A}}\), then there exists a sequence \(\tilde{\beta},\tilde{\beta}_1,\ldots,\tilde{\beta}_r,\tilde{\alpha}(\mathfrak{A})\) such that \(\tilde{\beta}_i\in N_{\mathfrak{A}},\ i=1,\ldots,r;\ \tilde{\beta}\leqslant\tilde{\beta}_1\leqslant\cdots\leqslant\tilde{\beta}_r\leqslant\tilde{\alpha}(\mathfrak{A})\), and the distance between neighboring elements of the sequence is equal to 1.

Definition 7. The layer \(S^k\) of the \(n\)-dimensional unit cube of number \(k\) is the set of all vertices \(\{\tilde{\gamma}\}\) such that \(\rho((0,\ldots,0),\tilde{\gamma})=k\). Clearly, the cardinality of \(S^k\) is \(C_n^k\).

Denote by \(B(N_\varphi)\) the collection of all distinct intervals entering into \(N_\varphi\).

In what follows, by the complexity of a d.n.f. we shall mean the number of elementary conjunctions entering into the d.n.f.

Denote by \(K_f(3^n)\) the number of conjunctions in a shortest d.n.f. of the function \(f(y_1,\ldots,y_k)\), i.e. a d.n.f. having minimal complexity.

Lemma 1. No interval \(N_{\mathfrak{A}}\subseteq N_f\) contains more than one upper point of the function \(f\).

Proof. Let \(\tilde{\alpha}\) and \(\tilde{\beta}\), \(\tilde{\alpha}\ne\tilde{\beta}\), be upper points of the function \(f(y_1,\ldots,y_k)\), \(N_{\mathfrak{A}}\subseteq N_f\), and \(\tilde{\alpha}\in N_{\mathfrak{A}},\ \tilde{\beta}\in N_{\mathfrak{A}}\). One of the points \(\tilde{\alpha},\tilde{\beta}\) is not the pole of the interval \(N_{\mathfrak{A}}\). Then, in view of Remark 2, this point is not an upper point for the function \(f(y_1,\ldots,y_k)\).

Corollary 1. The number of conjunctions in an arbitrary d.n.f. realizing \(f(y_1,\ldots,y_k)\) is not less than the number of upper points of the function \(f(y_1,\ldots,y_k)\).

Consider the family of functions \(\{\psi(x_1,\ldots,x_n)\}=\mathfrak{B}\) such that on the vertices \(\{\tilde{\gamma}\},\ \tilde{\gamma}\in S^k,\ k=[n/2]+2l+1\), the equality \(\psi(\tilde{\gamma})=1\) is fulfilled, where \(l\) is an integer such that \(0\leqslant k\leqslant n\). Denote
\[ \bigcup_{k=[n/2]+2l+1} S^k = W. \]

Remark 3. Clearly, the number \(l(n)\) of elements in \(\mathfrak{B}\) satisfies the inequality
\[ l(n)\geqslant 2^{2^{\,n-1}}. \]

Let \(\mathfrak{N}_\psi\) be a reduced d.n.f. of a function \(\psi\in\mathfrak{B}\), and let \(\mathfrak{A}\) be an elementary conjunction not entering into \(\mathfrak{N}_\psi\).

Lemma 2. The d.n.f. \(\mathfrak{N}_\psi\vee\mathfrak{A}\) is not a reduced d.n.f. for any function of the algebra of logic in the variables \(x_1,\ldots,x_n\).

Proof. 1. \(N_{\mathfrak{A}}\subseteq N_\psi\). Then the assertion is obvious in view of the uniqueness of the reduced d.n.f. for every Boolean function.

1. \(N_{\mathfrak{A}}\nsubseteq N_\psi\) \((N_{\mathfrak{A}}\ne E_n)\). Let \(\tilde{\alpha}=(\alpha_1,\ldots,\alpha_n)\in N_{\mathfrak{A}}\setminus N_\psi,\ \tilde{\alpha}\in W\).

Then \(B(N_\psi \vee \mathfrak A)\), together with \((\alpha_1,\ldots,\alpha_n)\), will contain all \(n\) edges joining \((\alpha_1,\ldots,\alpha_n)\) to points \(\tilde\beta\) such that \(\rho(\tilde\beta,(\alpha_1,\ldots,\alpha_n))=1\). (All such points lie in \(W\), and hence belong to \(N_\psi\).) In order that the D.N.F. \(N_\psi \vee \mathfrak A\) be a reduced D.N.F., it is necessary that all newly added edges be contained in \(N_{\mathfrak A}\), i.e. \(N_{\mathfrak A}\) must contain a ball with center at the point \((\alpha_1,\ldots,\alpha_n)\). But no interval, except \(E_n\), can contain a unit ball. Consequently, \(N_\psi \vee \mathfrak A\) is not a reduced D.N.F. for any function of the algebra of logic.

Corollary 2. From what has been proved it follows that the reduced D.N.F.’s of the functions of the family \(\mathfrak B\) correspond to the upper points of the function \(f(y_1,\ldots,y_k)\).

Remark 4. The cardinality of the set \(N_{f(y_1,\ldots,y_k)}\) is equal to \(2^{2^n}\).

From Corollaries 1 and 2 and Remarks 3 and 4 there follows the

Theorem.

\[ 2^{2^{\,n-1}} \leqslant K_f(3^n) \leqslant 2^{2^n}. \]

It follows from the theorem that the “characteristic” function \(f(y_1,\ldots,y_k)\) of reduced D.N.F.’s is very difficult to realize in the class of D.N.F.’s. The complexity of the shortest D.N.F. of the “characteristic” function is comparable with the complexity of the table (perfect D.N.F.) for \(f(y_1,\ldots,y_k)\).

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

Received
13 IV 1965

REFERENCES

1. S. V. Yablonskii, Tr. Mat. inst. im. V. A. Steklova AN SSSR, 51, 5 (1958).