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

✍ Scribed by Rimli Sengupta; H. Venkateswaran

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 128 KB
• Volume: 237
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00170-4

✦ Synopsis

Cancellations are known to be helpful in e cient algebraic computation of polynomials over ÿelds. We deÿne a notion of cancellation in Boolean circuits and deÿne Boolean circuits that do not use cancellation to be non-cancellative. 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 interpreted over GF(2). This non-monotone Boolean function is known to be in P. In the spirit of monotone complexity classes, we deÿne complexity classes based on non-cancellative Boolean circuits. We show that when the Boolean circuit model is restricted by withholding cancellation, P and popular classes within P are restricted as well, but NP and circuit deÿnable classes above it remain unchanged.