Lower bounds for Boolean circuits of bounded negation width
(2022) In Journal of Computer and System Sciences 129. p.90-105- Abstract
The negation width of a Boolean AND, OR, NOT circuit computing a monotone Boolean function f is the minimum number w such that the unique formal DNF produced (purely syntactically) by the circuit contains each prime implicant of f extended by at most w solely negated variables. The negation width of monotone circuits is zero. We first show that already a moderate allowed negation width can substantially decrease the size of monotone circuits. Our main result is a general reduction: if a monotone Boolean function f can be computed by a non-monotone circuit of size s and negation width w, then f can be also computed by a monotone circuit of size s times 4min{wm,mw}logM, where m is the maximum length of a prime... (More)
The negation width of a Boolean AND, OR, NOT circuit computing a monotone Boolean function f is the minimum number w such that the unique formal DNF produced (purely syntactically) by the circuit contains each prime implicant of f extended by at most w solely negated variables. The negation width of monotone circuits is zero. We first show that already a moderate allowed negation width can substantially decrease the size of monotone circuits. Our main result is a general reduction: if a monotone Boolean function f can be computed by a non-monotone circuit of size s and negation width w, then f can be also computed by a monotone circuit of size s times 4min{wm,mw}logM, where m is the maximum length of a prime implicant and M is the total number of prime implicants of f.
(Less)
- author
- Jukna, Stasys and Lingas, Andrzej LU
- organization
- publishing date
- 2022-11
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Boolean circuits, Lower bounds, Monotone circuits
- in
- Journal of Computer and System Sciences
- volume
- 129
- pages
- 16 pages
- publisher
- Elsevier
- external identifiers
-
- scopus:85131420088
- ISSN
- 0022-0000
- DOI
- 10.1016/j.jcss.2022.05.003
- language
- English
- LU publication?
- yes
- id
- 528f3d99-f3c7-47f5-ba75-ec109baad44c
- date added to LUP
- 2022-08-18 13:09:57
- date last changed
- 2022-08-18 13:09:57
@article{528f3d99-f3c7-47f5-ba75-ec109baad44c, abstract = {{<p>The negation width of a Boolean AND, OR, NOT circuit computing a monotone Boolean function f is the minimum number w such that the unique formal DNF produced (purely syntactically) by the circuit contains each prime implicant of f extended by at most w solely negated variables. The negation width of monotone circuits is zero. We first show that already a moderate allowed negation width can substantially decrease the size of monotone circuits. Our main result is a general reduction: if a monotone Boolean function f can be computed by a non-monotone circuit of size s and negation width w, then f can be also computed by a monotone circuit of size s times 4min{w<sup>m</sup>,m<sup>w</sup>}logM, where m is the maximum length of a prime implicant and M is the total number of prime implicants of f.</p>}}, author = {{Jukna, Stasys and Lingas, Andrzej}}, issn = {{0022-0000}}, keywords = {{Boolean circuits; Lower bounds; Monotone circuits}}, language = {{eng}}, pages = {{90--105}}, publisher = {{Elsevier}}, series = {{Journal of Computer and System Sciences}}, title = {{Lower bounds for Boolean circuits of bounded negation width}}, url = {{http://dx.doi.org/10.1016/j.jcss.2022.05.003}}, doi = {{10.1016/j.jcss.2022.05.003}}, volume = {{129}}, year = {{2022}}, }