Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Lower bounds for Boolean circuits of bounded negation width

Jukna, Stasys and Lingas, Andrzej LU (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}log⁡M, 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}log⁡M, where m is the maximum length of a prime implicant and M is the total number of prime implicants of f.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
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>}log⁡M, 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}},
}