Negation-limited Circuit Complexity<p>

Recently there has been substantial progress in obtaining strong
lower bounds on size of monotone circuits computing certain Boolean
functions. It is natural to ask if we could put together and make
use of the approaches developed so far for the monotone case to derive
strong lower bounds for more general models. For such a generalized
model we consider circuits with a limited number of negation gates
and obtain superpolynomial lower bound for circuits computing
certain NP complete problem.