2015 | OriginalPaper | Buchkapitel
Comparator Circuits over Finite Bounded Posets
verfasst von : Balagopal Komarath, Jayalal Sarma, K. S. Sunil
Erschienen in: Automata, Languages, and Programming
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
Comparator circuit model was originally introduced in [
4
] (and further studied in [
2
]) to capture problems which are not known to be
P
-complete but still not known to admit efficient parallel algorithms. The class
CC
is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem and we know that
NLOG
$$\subseteq $$
⊆
CC
$$\subseteq $$
⊆
P
. Cook
et al
[
2
] showed that
CC
is also the class of languages decided by polynomial size comparator circuits.
We study generalizations of the comparator circuit model that work over fixed finite bounded posets. We observe that there are universal comparator circuits even over arbitrary fixed finite bounded posets. Building on this, we show that general (resp. skew) comparator circuits of polynomial size over fixed finite
distributive
lattices characterizes
CC
(resp.
LOG
). Complementing this, we show that general comparator circuits of polynomial size over arbitrary fixed finite lattices exactly characterizes
P
and that when the comparator circuit is skew they characterize
NLOG
. In addition, we show a characterization of the class
NP
by a family of polynomial sized comparator circuits over fixed
finite bounded posets
. These results generalize the results in [
2
] regarding the power of comparator circuits. As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira’s theorem[
5
] can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture exactly
NC
$$^1$$
1
.
Our techniques involve design of comparator circuits and finite posets. We then use known results from lattice theory to show that the posets that we obtain can be embedded into appropriate lattices. Our results gives new methods to establish
CC
upper bound for problems also indicate potential new approaches towards the problems
P
vs
CC
and
NLOG
vs
LOG
using lattice theoretic methods.