III is SAT, which is polynomial if P = NP.

I is equivalent to answering a problem if you can satisfy the equation (C and NOT D) or (D and NOT C). If you can, then you circuits are not equivalent (there is an input for which C is 1 and D is 0, or vice versa). Again, this is SAT. So, I and III, because you have no choice I and III, but only I, II, III, this is likely to be the answer.

## Bookmarks