Name
Abstract | ||
|---|---|---|
From a theorem of Markov, the minimum number of negation gates in a circuit sufficient to compute any collection of Boolean functions on n variable is ℓ = ⌈log(n+1)⌉. Santha and Wilson (SIAM Journal of Computing 22(2):294-302 (1993)) showed that in some classes of bounded-depth circuits ℓ negation gates are no longer sufficient for some explicitly defined Boolean function. In this paper, we consider a general class of bounded-depth circuits in which each gate computes an arbitrary monotone Boolean function or its negation. Our purpose is to extend the theorem of Markov for such a general class of circuits. We first show that a lower bound shown by Santha and Wilson becomes an extension of Markov's lower bound by a small refinement. Then, we present tight upper bounds on the number of negations for computing an arbitrary collection of Boolean functions. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-24587-2_13 | International Symposium on Algorithms and Computation |
Keywords | Field | DocType |
boolean function,circuit complexity,negation-limited circuits,fight bound,sufficient number,bounded-depth circuit,arbitrary monotone boolean function,computational complexity,arbitrary collection,lower bound,upper bound | Karp–Lipton theorem,Boolean function,Discrete mathematics,Combinatorics,Boolean circuit,Parity function,Product term,And-inverter graph,Circuit minimization for Boolean functions,Boolean expression,Mathematics | Journal |
Volume | Issue | ISSN |
90 | 1 | 0302-9743 |
Citations | PageRank | References |
8 | 0.66 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shao Chin Sung | 1 | 113 | 9.72 |
| Keisuke Tanaka | 2 | 278 | 19.04 |