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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for reduced polynomial
Python Polynomial Regression with Scikit-learn