Abstract
It is proven that monotone circuits computing the perfect matching function on n-vertex graphs require Ω1992 depth. This implies an exponential gap between the depth of monotone and nonmonotone circuits.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 736-744 |
| Number of pages | 9 |
| Journal | Journal of the ACM (JACM) |
| Volume | 39 |
| Issue number | 3 |
| DOIs | |
| State | Published - Jan 7 1992 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- circuit depth
- monotone computation
- perfect matching