[P=NP] question

[neikel]

There are two circuits C and D, consisting of only AND, OR, and NOT. Each circuit has n

inputs, and a single output. Suppose that P=NP, which of the following can be

computed in polynomial time:

I. The equivalence of C and D.

II. Whether there exist a smaller circuit than C that is equivalent to C.

III. Whether there exist an input to C which returns 1.

(A) I (B) II © II and III (D) I, II, and III (E) None of the above

 

Which is your choice ?

[itman]

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.