Comparator circuits over finite bounded posets

DOI10.1007/978-3-662-47672-7_68zbMATH Open1394.68155arXiv1503.00275OpenAlexW3023000450MaRDI QIDQ1640992FDOQ1640992

Balagopal Komarath, Jayalal Sarma M. N., K. S. Sunil

Publication date: 14 June 2018

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: Comparator circuit model was originally introduced by Mayr and Subramanian (1992) (and further studied by Cook, Filmus and Le (2012)) 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 NL is contained in CC which is inturn contained in P. Cook, Filmus and Le (2012) 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. L). Complementing this, we show that general comparator circuits of polynomial size over arbitrary fixed finite lattices exactly characterizes P even when the comparator circuit is skew. In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed {em finite bounded posets}. These results generalize the results by Cook, Filmus and Le (2012) regarding the power of comparator circuits. As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira's theorem (1971) can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture exactly NC^1.

Full work available at URL: https://arxiv.org/abs/1503.00275

Recommendations

• Comparator circuits over finite bounded posets
• Lower Bounds for (Non-Monotone) Comparator Circuits
• Algorithms and lower bounds for comparator circuits from shrinkage
• Optimal Conclusive Sets for Comparator Networks
• Optimal conclusive sets for comparator networks
• scientific article; zbMATH DE number 4008288
• The complexity of the comparator circuit value problem
• Publication:4936897
• Comparability Graphs and Digital Topology
• Circuits in bounded arithmetic. I

zbMATH Keywords

polynomial-size circuitscomparator circuitslogspace computation

Mathematics Subject Classification ID

Partial orders, general (06A06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Computational Complexity
• Title not available (Why is that?)
• The complexity of circuit value and network stability
• Every finite lattice can be embedded in a finite partition lattice
• Title not available (Why is that?)
• The complexity of the comparator circuit value problem

Cited In (3)

• Title not available (Why is that?)
• Algorithms and lower bounds for comparator circuits from shrinkage
• Comparator circuits over finite bounded posets

This page was built for publication: Comparator circuits over finite bounded posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1640992)