Two boolean expressions equivalence. Co-NP?
<p><strong>PROBLEM</strong> : <em>Having two boolean formulas we need to say if they have the same truth table</em></p>

<p>Ex: <code>(x1 v x2)∧(¬x1 v x3)</code>   and <code>(¬x1 ∧ x2) v (x1 ∧ x3)</code> have the same values for all the combinations of (x1, x2, x3)</p>

<p>I have a few ideas: this problem may be at least as hard as the Tautology problem.</p>

<p>It might be easier to prove the correctness of an "NO" answer, than an "YES" one (Co-NP), but I don't know how to proove it.
Also, what is the certificate in here? Is it the answer "YES" or "NO" ?</p>

<p>Any ideas? Thanks.</p>