| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4952277 | Theoretical Computer Science | 2017 | 11 Pages |
Abstract
Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and study the connection of negation-limited formulas with negation-limited circuits and with monotone formulas. We show the following results:
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Siyao Guo, Ilan Komargodski,