checking boolean logical equivalence

Question

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?

Answer 1

It's actually co-NP-Complete.

Here's the proof.

First we have to show that it's in co-NP. This isn't hard, since it's quick to verify a counterexample showing that the two Boolean formulas are not equivalent.

Then we have to show a problem known to be co-NP-complete reduces to your problem, which we'll call Boolean Equivalence. We'll reduce the Tautology problem to Boolean Equivalence. So if we want to determine whether a given wff $\phi$ is a Tautology, we simply send the formulas $\phi$ and $a \vee \neg a$ into the Boolean Equivalence tester. Since this can be done in polynomial time, we're done.