Non-cancellative Boolean circuits: A generalization of monotone Boolean circuits

Cancellations are known to be helpful in efficient algebraic computation of polynomials over fields. We define a notion of cancellation in Boolean cir cuits and define Boolean circuits that do not use cancellation to be non-ca ncellative. Non-cancellative Boolean circuits are a natural generalization of monotone Boolean circuits. We show that in the absence of cancellation, Boolean circuits require super-polynomial size to compute the determinant i nterpreted over GF(2). This non-monotone Boolean function is known to be in P. In the spirit of monotone complexity classes, we define complexity clas ses based on non-cancellative Boolean circuits. We show that when the Boole an circuit model is restricted by withholding cancellation, P and popular c lasses within P are restricted as well, but N P and circuit definable class es above it remain unchanged. (C) 2000 Elsevier Science B.V. All rights res erved.