Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Co-NP reduced in polynomial-time

  1. Aug 2, 2013 #1
    Every language in co-NP can be reduced in polynomial-time to an instance of [itex]\forall x P(x)[/itex] for some Boolean formula with a single bound variable and no free variables, right?
  2. jcsd
  3. Aug 5, 2013 #2
    A definition of a language being in co-NP would be that such an instance exists and the predicate is polynomial-time computable. I'm not sure if this is what you are getting at.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Co-NP reduced in polynomial-time
  1. P = NP problem (Replies: 3)

  2. P=NP Explanation (Replies: 1)

  3. P does equal NP? (Replies: 5)

  4. NP complete problems (Replies: 4)