Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-035 | 19th July 2017 12:29

Comparator Circuits over Finite Bounded Posets

RSS-Feed




Revision #1
Authors: Sunil K S, Balagopal Komarath, Jayalal Sarma
Accepted on: 19th July 2017 12:29
Downloads: 779
Keywords: 


Abstract:

The comparator circuit model was originally introduced by Mayr and Subramanian (1992) (and further studied by Cook et. al. (2014)) to capture problems that 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. (2014) showed that CC is also the class of languages decided by polynomial size comparator circuit families.

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 the following :

- Comparator circuits of polynomial size over fixed finite distributive lattices characterize the class CC. When the circuit is restricted to be skew, they characterize LOG. Noting that (uniform) polynomial sized Boolean circuits (resp. skew) characterize P (resp. NLOG), this indicates a comparison between P vs CC and NLOG vs LOG problems.

- Complementing this, we show that comparator circuits of polynomial size over arbitrary
fixed finite lattices characterize the class 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 finite bounded posets. 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 the class NC^1.

These results generalize results by Cook et. al. (2014) regarding the power of comparator circuits. 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 give new methods to establish CC upper bounds for problems and also indicate potential new approaches towards the problems P vs CC and NLOG vs LOG using lattice theoretic methods.



Changes to previous version:

In the earlier version, we erroneously claimed that poly-size skew comparator circuit families over lattices characterize NL when in fact they characterize P.


Paper:

TR15-035 | 22nd February 2015 14:47

Comparator Circuits over Finite Bounded Posets





TR15-035
Authors: Sunil K S, Balagopal Komarath, Jayalal Sarma
Publication: 10th March 2015 22:48
Downloads: 1766
Keywords: 


Abstract:

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) 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 We know that NL is a subset of CC (See Feder's algorithm described in Subramanian's PhD thesis (1990)) and CC is a subset of P. Cook, Filmus and Le (2012) showed that CC is also the class of languages decided by uniform 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 the following

(1) Comparator circuits of polynomial size over fixed finite distributive lattices characterizes CC. When the circuit is restricted to be skew, they characterize L. Noting that (uniform) polynomial sized Boolean circuits (resp. skew) characterize P (resp. NL), this indicates a comparison between P vs CC and NL vs L problems.

(2) Complementing this, we show that comparator circuits of polynomial size over arbitrary fixed finite lattices exactly characterize P and that when the comparator circuit is skew they characterize NL. This provides an additional comparison between P vs CC and NL vs L problems. The lattice that we design to prove this result is non-distributive and cannot be embedded into any distributive lattice preserving meets and joins.

(3) In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed finite bounded posets. 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$.

These results generalize the results by Cook et al (2012) regarding the power of comparator circuits. 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 NL vs L using lattice theoretic methods.



ISSN 1433-8092 | Imprint