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. 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 $\Psi \wedge D_n$ computes a read-once function, where $D_n$ is as above and $\Psi$ is the $\bigwedge -\bigvee -\bigwedge$ depth-3 read-once monotone Boolean formula (so that the entire expression $\Psi \wedge D_n$ is depth-3 read-2). This result improves the result of \cite{elbassioni2011readability} in the depth and the result of \cite{gurvich2010it} in the readability of the input formula.