Sponsored Ad:
Results 1 to 2 of 2

Thread: [P=NP] question

  1. #1
    Trying to make mom and pop proud
    Join Date
    Oct 2008
    Rep Power

    Good post? Yes | No

    [P=NP] question

    Sponsored Ad:
    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

    Which is your choice ?

  2. #2
    Trying to make mom and pop proud
    Join Date
    Oct 2011
    Rep Power

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

Thread Information

Users Browsing this Thread

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

Similar Threads

  1. Replies: 3
    Last Post: 01-06-2011, 06:17 PM
  2. Replies: 2
    Last Post: 09-22-2008, 04:52 PM
  3. Small question about Listening question of Toefl ibt
    By cielbleu in forum TOEFL Listening
    Replies: 3
    Last Post: 08-03-2008, 07:08 PM
  4. Mixtures question from GMAT PREP - 700+ level question -Need Help
    By adiknish in forum GMAT Data Sufficiency
    Replies: 4
    Last Post: 07-14-2006, 02:43 PM
  5. height/time question: Real gmat question?
    By zzhop in forum GMAT Problem Solving
    Replies: 8
    Last Post: 01-17-2006, 06:16 PM

Posting Permissions

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