<p>Corollary 3.5 of [BHR84] shows that the problem is coNP-complete.</p>

<p>[BHR84] P. A. Bloniarz, H. B. Hunt, III, and D. J. Rosenkrantz.  Algebraic structures with hard equivalence and minimization problems.  <em>Journal of the ACM</em>, 31(4):879–904, Oct. 1984.  <a href="http://dx.doi.org/10.1145/1634.1639">http://dx.doi.org/10.1145/1634.1639</a></p>

CC BY-SA 3.0
2011-07-22T00:31:03.907Z
2011-07-22T00:31:03.907Z
Tsuyoshi Ito
<p>Is the following problem in PTIME, or coNP-hard:</p>

<p>Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ and $\vee$). Decide whether $e_1 \equiv e_2$, that is they have the same value for all assignments to the variables.</p>

<p>If both expressions would be given in DNF, then the problem is in PTIME since we could first lexicographically order the conjunctive clauses and compare. But bringing an arbitrary expression to DNF can blow up exponentially. A similar argument seems to hold for binary-decision-diagrams.</p>

<p>Obviously, the problem is in coNP.</p>

<p>I was Googling around a fair amount, but couldn't find any answer. </p>

<p>Apologies for the elementary question.</p>

<cc.complexity-theory><time-complexity><boolean-functions><monotone>
Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?
danielzinn
# Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?

(Asked by: username_0 on 2011-07-21)

Is the following problem in PTIME, or coNP-hard:

Given two Boolean expressions $e\_1$ and $e\_2$ in variables $x\_1,\dots,x\_n$, without negation (ie, the expressions are entirely built up via $\wedge$ and $\vee$). Decide whether $e\_1 \equiv e\_2$, that is they have the same value for all assignments to the variables.

If both expressions would be given in DNF, then the problem is in PTIME since we could first lexicographically order the conjunctive clauses and compare. But bringing an arbitrary expression to DNF can blow up exponentially. A similar argument seems to hold for binary-decision-diagrams.

Obviously, the problem is in coNP.

I was Googling around a fair amount, but couldn't find any answer.

Apologies for the elementary question.

**Tags:** cc.complexity-theory, time-complexity, boolean-functions, monotone


---

## 1 answers

### Answer by username_1 on 2011-07-22. Score: 14 | Accepted answer

Corollary 3.5 of [BHR84] shows that the problem is coNP-complete.

[BHR84] P. A. Bloniarz, H. B. Hunt, III, and D. J. Rosenkrantz. Algebraic structures with hard equivalence and minimization problems. *Journal of the ACM*, 31(4):879–904, Oct. 1984. <http://dx.doi.org/10.1145/1634.1639>


---

