# Co-NP reduced in polynomial-time

1. Aug 2, 2013

### Dragonfall

Every language in co-NP can be reduced in polynomial-time to an instance of $\forall x P(x)$ for some Boolean formula with a single bound variable and no free variables, right?

2. Aug 5, 2013

### psicicle

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.