Recognizing Read-Once Functions from Depth-Three Formulas

Abstract

Consider the following decision problem: for a given monotone Boolean function f decide, whether f is read-once. For this problem, it is essential how the input function f is represented. On a negative side we have the following results. Elbassioni et al. [1] proved that this problem is coNP-complete when f is given by a depth-4 read-2 monotone Boolean formula. Gurvich [2] proved that this problem is coNP-complete even when the input is the following expression: $C\vee D_n$, where $D_n = x_1 y_1 \vee \ldots \vee x_n y_n$ and C is a monotone CNF over the variables $x_1, y_1, \ldots , x_n, y_n$ (note that this expression is a monotone Boolean formula of depth 3; in [2] nothing is said about the readability of C, but the proof is valid even if C is read-2 and thus the entire formula is read-3).

On a positive side, from [3] we know that there is a polynomial time algorithm to recognize read-once functions when the input is a monotone depth-2 formula (that is, a DNF or a CNF). There are even very fast algorithms for this problem [4].

Our contribution consists of the following two results. We show that we can test in polynomial-time whether a given expression $C\vee D$ computes a read-once function, provided that C is a read-once monotone CNF and D is a read-once monotone DNF and all the variables of C occur also in D (recall that due to Gurvich, the problem is coNP-complete when C is read-2). The second result states that this is a coNP-complete problem to decide whether the expression $A\wedge D_n$ computes a read-once function, where $D_n$ is as above and A is the $\bigwedge -\bigvee -\bigwedge$ depth-3 read-once monotone Boolean formula (so that the entire expression $A\wedge D_n$ is depth-3 read-2). This result improves the result of [1] in the depth and the result of [2] in the readability of the input formula.

A. Kozachinskiy—Supported in part by the RFBR grant 16-01-00362 and by the Russian Academic Excellence Project ‘5-100’.

Appendices

Appendix

A Proof of Lemma 3

Let T be a maxterm of $C\vee D$ and $C_u, C_v \subset T$. For the sake of contradiction assume that there is $j\in \{1, \ldots , l\}$ such that $|(C_u\cup C_v) \cap D_j| \ge 2$. Pick any two distinct $p, q\in (C_u\cup C_v) \cap D_j$. Let us show that $(C\vee D)(T{\setminus }\{q\} \rightarrow 0) = 0$. To show that $C(T{\setminus }\{q\} \rightarrow 0) = 0$ observe that $C_u$ or $C_v$ does not contain q and hence $C_u\subset T{\setminus }\{q\}$ or $C_v \subset T{\setminus }\{q\}$. To show that $D(T{\setminus }\{q\} \rightarrow 0) = 0$ observe that $D(T\rightarrow 0) = 0$ and hence T intersects all sets $D_1, \ldots , D_l$. Since $q\in D_j$ and hence $q\notin D_i$ for all $i\ne j$, the set $T{\setminus }\{q\}$ still intersects $D_i$ for all $i\ne j$. And it intersects $D_j$ since $p\in C_u\cup C_v\subset T$ and p was not removed from T. Since T is a maxterm, this is a contradiction.

On the other hand, assume that for every $j\in \{1, \ldots , l\}$ it holds that $|(C_u\cup C_v) \cap D_j| \le 1$. We have to find a maxterm T that includes both $C_u,C_v$. Start with $T=C_u\cup C_v$. Then for all j such that $D_j$ does not intersect $C_u\cup C_v$ pick a variable from $D_j$ and include it in T. In this way we make T intersect every $D_j$ in exactly one point. In particular, $D(T\rightarrow 0) = 0$ and $C(T\rightarrow 0) = 0$. On the other hand, every proper subset $T^\prime$ of T is disjoint with at least one $D_j$ and hence $D(T^\prime \rightarrow 0) = 1$. This shows that T is a maxterm.

B Proof of Lemma 4

Since $C\rightarrow D$ is not a tautology, $C_i$ is non-empty and intersects with some $D_j$. Further, without loss of generality we may assume that:

• $i = 1$;

• $C_1$ intersects with $D_1, \ldots D_r$ and $C_1$ is disjoint with $D_{r + 1}, \ldots D_l$ for some $1 \le r \le l$;

• $C_2, \ldots , C_s$ all intersect with $D_1 \cup D_2 \cup \ldots \cup D_r$ and $C_{s + 1}, \ldots , C_m$ are all disjoint with $D_1 \cup D_2 \cup \ldots \cup D_r$ for some $1 \le s \le m$.

From the fact that $D_1 \cup D_2 \cup \ldots \cup D_l = \{x_1, \ldots , x_n\}$ we may derive that:

$$\begin{aligned} C_{s + 1}, \ldots , C_{m} \subset D_{r + 1} \cup \ldots \cup D_l. \end{aligned}$$

(1)

Define an auxiliary CNF $\widehat{C}= C_{s + 1} \wedge \ldots \wedge C_{m}$ and an auxiliary DNF $\widehat{D}= D_{r + 1} \vee \ldots \vee D_l$. Note that $\widehat{C}$ and $\widehat{D}$ are over variables from $D_{r + 1} \cup \ldots \cup D_l$ (this follows from (1)).

We claim that there exists T such that T is a maxterm of $C\vee D$ and $C_1\subset T$ if and only if $\widehat{C}\rightarrow \widehat{D}$ is not a tautology (the latter by Lemma 1 can be verified in polynomial time).

($\Leftarrow$) Assume that $\widehat{C}\rightarrow \widehat{D}$ is not a tautology. Then there exists $\widehat{T}\subset D_{r + 1} \cup \ldots \cup D_l$ such that

$$\begin{aligned} C_{s + 1} \not \subset \widehat{T}, \ldots , C_m \not \subset \widehat{T}; \end{aligned}$$

(2)

$$\begin{aligned} |D_{r + 1} \cap \widehat{T}| = 1, \ldots , |D_{l} \cap \widehat{T}| = 1; \end{aligned}$$

(3)

(take minimal $\widehat{T}\subset D_{r + 1} \cup \ldots \cup D_l$ such that $\widehat{C}(\widehat{T}\rightarrow 0) = 1$ and $\widehat{D}(\widehat{T}\rightarrow 0) = 0$).

Let us show that $T = \widehat{T}\cup C_1$ is the maxterm of $C\vee D$. First of all, let us verify that $(C\vee D)(T\rightarrow 0) = 0$. Indeed,

• $C(T\rightarrow 0) = 0$ because $C_1 \subset T$;

• $D(T\rightarrow 0) = 0$ because every $D_1, \ldots , D_l$ intersects with T; namely, $D_1, \ldots D_r$ intersect $C_1$ and $D_{r + 1}, \ldots , D_l$ intersect $\widehat{T}$.

Now, assume that $T^\prime \subset T$ and $(C\vee D)(T^\prime \rightarrow 0) = 0$. Let us show that this is possible only when $T^\prime = T$.

Since $D(T^\prime \rightarrow 0) = 0$, we have that $T^\prime$ intersects with every $D_1, \ldots , D_l$. From the fact that $C_1$ is disjoint with $D_{r + 1}, \ldots , D_l$ and from (3) it follows that $\widehat{T}\subset T^\prime$.

It remains to show that $C_1 \subset T^\prime$. This follows from the assumption that $C(T^\prime \rightarrow 0) = 0$. Indeed, then at least one clause of C should be the subset of $T^\prime$. Assume that this clause is $C_u$. If $C_u \ne C_1$, then $C_u\subset \widehat{T}$. There are two cases:

• The first case. Assume that $C_u \in \{C_2, \ldots , C_s\}$. Then $C_u\subset \widehat{T}\subset D_{r + 1} \cup \ldots \cup D_l$ intersects with $D_1 \cup D_2 \cup \ldots \cup D_r$, but the latter is impossible.

• The second case. Assume that $C_u \in \{C_{s + 1}, \ldots , C_m\}$. This case contradicts (2).

($\Rightarrow$) Assume that T is the maxterm of $C\vee D$ such that $C_1 \subset T$. Define $\widehat{T}= T{\setminus }C_1$. Later we will show that $\widehat{C}(\widehat{T}\rightarrow 0) = 1$, $\widehat{D}(\widehat{T}\rightarrow 0) = 0$ and hence $\widehat{C}\rightarrow \widehat{D}$ is not a tautology. But at first we should verify that $\widehat{T}\subset D_{r + 1} \cup \ldots \cup D_l$ (recall that $\widehat{C}, \widehat{D}$ are over variables from $D_{r + 1} \cup \ldots \cup D_l$).

To show that $\widehat{T}\subset D_{r + 1} \cup \ldots \cup D_l$ assume for contradiction that $\widehat{T}$ intersects $D_1 \cup D_2 \cup \ldots \cup D_r$ and let q be the variable which lies in their intersection. Note that $q\notin C_1$ (this is because $q\in \widehat{T}= T{\setminus }C_1$). Let us demonstrate that for such q we have that $(C\vee D)(T{\setminus }\{q\} \rightarrow 0) = 0$ (this is already a contradiction since T is a maxterm). Indeed, $C(T{\setminus }\{q\} \rightarrow 0) = 0$ since $C_1 \subset T{\setminus }\{q\}$. Further, we should show that $T{\setminus }\{q\}$ intersects every $D_1, \ldots D_l$ and hence $D(T{\setminus }\{q\} \rightarrow 0) = 0$. Indeed:

• $T{\setminus }\{q\}$ intersects $D_1, \ldots , D_r$ because of $C_1$;

• $T{\setminus }\{q\}$ intersects $D_{r + 1}, \ldots , D_{l}$ because of the following two reasons: (a) $D(T\rightarrow 0) = 0$ and hence T intersects every $D_{r + 1}, \ldots , D_l$; (b) q is not in $D_{r + 1}\cup \ldots \cup D_l$.

Thus it remains to show that $\widehat{C}(\widehat{T}\rightarrow 0) = 1$ and $\widehat{D}(\widehat{T}\rightarrow 0) = 0$. To show that the first equality is true assume for contradiction that there is $C_u \in \{C_{s + 1}, \ldots , C_m\}$ such that $C_u \subset \widehat{T}= T{\setminus }C_1$. But then $C_u \subset T$. This contradicts the assumption that there is no maxterm of $C\vee D$ which contains two distinct clauses of C.

To show that the second equality ($\widehat{D}(\widehat{T}\rightarrow 0) = 0$) is true, observe that $\widehat{T}$ intersects every $D_{r + 1}, \ldots , D_l$. This is true because $D(\widehat{T}\rightarrow 0) = 0$ and hence T intersects $D_{r + 1}, \ldots , D_l$; but $C_1$ by assumption is disjoint with $D_{r + 1}, \ldots , D_l$ and hence $T{\setminus }C_1$ still intersects them.

C Proof of Lemma 5

If there is $C_i$ such that $a, b\in C_i$ or $\{a, b\} \not \subset C_1 \cup \ldots \cup C_m$, then no left minterm S can contain both a and b. From now we assume that this is not the case, i.e. there is no $C_i$ which contains both a and b and $a, b\in C_1\cup \ldots \cup C_m$. Let $\widehat{C}\vee \widehat{D}$ be obtained from $C\vee D$ by setting a, b to 1. In other words, $\widehat{C}$ is obtained from C by erasing all clauses containing a or b and $\widehat{D}$ is obtained from D by erasing a and b. Assume without loss of generality that $C_1, C_2$ are erased clauses, $a\in C_1, b\in C_2$ and $D_1, \ldots , D_r$ are conjunctions containing a or b (note that r is either 1 or 2). Then $\widehat{C}$ and $\widehat{D}$ can be written as

$$\widehat{C}= C_{3} \wedge \ldots \wedge C_m,$$

$$\widehat{D}= (D_1{\setminus }\{a, b\}) \vee \ldots \vee (D_r{\setminus }\{a, b\}) \vee D_{r + 1} \vee \ldots \vee D_l.$$

We assert that there is a left minterm S containing a and b iff $\widehat{C}\rightarrow \widehat{D}$ is not a tautology. The latter by Lemma 1 can be verified in polynomial times.

($\Leftarrow$) Assume that $\widehat{C}\rightarrow \widehat{D}$ is not a tautology. Take minimal $\widehat{S}\subset \{x_1, \ldots , x_n\}{\setminus }\{a, b\}$ such that $\widehat{C}(\widehat{S}\rightarrow 1) = 1, \widehat{D}(\widehat{S}\rightarrow 1) = 0$. Obviously, such $\widehat{S}$ satisfies the following two conditions:

$$\begin{aligned} \widehat{S}\subset C_{3} \cup \ldots \cup C_m, \qquad |\widehat{S}\cap C_{3}| = 1, \ldots , |\widehat{S}\cap C_m| = 1, \end{aligned}$$

(4)

$$\begin{aligned} D_1{\setminus }\{a, b\} \not \subset \widehat{S}, \ldots , D_r{\setminus }\{a, b\} \not \subset \widehat{S},\,\, D_{r + 1} \not \subset \widehat{S}, \ldots , D_l\not \subset \widehat{S}. \end{aligned}$$

(5)

Now, define $S = \widehat{S}\cup \{a, b\}$. Let us show that S is a left minterm of $C\vee D$. From (5) it follows that there is no $j \in \{1, \ldots , l\}$ such that $D_j\subset S$. Hence S contains no right set as a proper subset. Thus it remains to show by Lemma 2 that S is a left set. Since a, b are from $C_1 \cup \ldots \cup C_m$, we have that

$$ S\subset (\{a, b\} \cup C_{3} \cup \ldots \cup C_m) \subset C_1 \cup \ldots \cup C_m. $$

Moreover, S intersects every clause of C in exactly one point. For $C_{3}, \ldots , C_m$ this follows from (4) and from the fact that $C_{3}, \ldots , C_m$ contain neither a nor b. For $C_1, C_2$ this is true because: (a) $\widehat{S}$ is disjoint with $C_1, C_2$; (b) $a\in C_1, b\in C_2$.

($\Rightarrow$) Assume that there is a left minterm S of $C\vee D$ containing a and b. Define $\widehat{S}= S{\setminus }\{a, b\}$. Let us show that $\widehat{S}$ intersects every $C_3, \ldots C_m$. Indeed, this is true for S and a, b are not from $C_3\cup \ldots \cup C_m$. Hence $\widehat{C}(\widehat{S}\rightarrow 1) = 1$. On the other hand, $\widehat{D}(\widehat{S}\rightarrow 1) = 0$, since:

• $D_1{\setminus }\{a, b\} \not \subset \widehat{S}, \ldots D_r{\setminus }\{a, b\}\not \subset \widehat{S}$ because otherwise at least one $D_1, \ldots , D_r$ is the subset of $S = \widehat{S}\cup \{a, b\}$;

• $D_{r + 1}\not \subset \widehat{S}, \ldots , D_l \not \subset \widehat{S}$ because it is true even for S.

Thus $\widehat{C}\rightarrow \widehat{D}$ is not a tautology.