Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Reductions for Monotone Boolean Circuits
verfasst von : Kazuo Iwama, Hiroki Morizumi
Erschienen in: Mathematical Foundations of Computer Science 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The large class, say
NLOG
, of Boolean functions, including 0-1 Sort and 0-1 Merge, have an upper bound of
O
(
n
log
n
) for their monotone circuit size, i.e., have circuits with
O
(
n
log
n
) AND/OR gates of fan-in two. Suppose that we can use, besides such normal AND/OR gates, any number of more powerful “
F
-gates” which realize a monotone Boolean function
F
with
r
(≥2) inputs and
r
′ (≥1) outputs. Note that the cost of each AND/OR gate is one and we assume that the cost of each
F
-gate is
r
. Now we define: A Boolean function
f
in NLOG is said to be
F
-Easy if
f
can be constructed by a circuit with AND/OR/
F
gates whose total cost is
o
(
n
log
n
). In this paper we show that 0-1 Merge is not
F
-Easy for an arbitrary monotone function
F
such that
r
′ ≤
r
/log
r
.