Get all the updates for this publication

Conferences

Comparator circuits over finite bounded posetsOpen Access

Published in Springer Verlag

2015

Volume: 9134

Pages: 834 - 845

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 ⊆ CC ⊆ 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 NC1. 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. © Springer-Verlag Berlin Heidelberg 2015.

Topics: Comparator (53)%53% related to the paper, Boolean circuit (52)%52% related to the paper and Complexity class (51)%51% related to the paper

View more info for "Comparator Circuits over Finite Bounded Posets"

Preprint Version

Content may be subject to copyright.This is a green open access articleThis is a green open access article

About the journal

Journal | Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Publisher | Data powered by TypesetSpringer Verlag |

ISSN | 03029743 |

Open Access | Yes |

Concepts (20)

- Algorithms
- AUTOMATA THEORY
- Boolean algebra
- Circuit simulation
- Circuit theory
- Comparator circuits
- Comparators (optical)
- Computational linguistics
- Lattice theory
- Polynomials
- Set theory
- Boolean formulae
- CIRCUIT VALUE PROBLEM
- Complexity class
- DISTRIBUTIVE LATTICE
- FINITE LATTICES
- New approaches
- Polynomial size
- Upper bound
- Electric network analysis