1. Good post? |

[P=NP] question

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 (C) II and III (D) I, II, and III (E) None of the above

2. Good post? |
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.

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•