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 logspacereducible 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 arbitraryfixed 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 latticetheory 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.
展开▼
机译：比较器电路模型最初是由Mayr和Subramanian（1992）引入的（并由Cook等人（2014）进一步研究），以捕获未知的问题，这些问题未知是P完全的，但仍然不知道可以使用有效的并行算法。 CC类是问题的复杂性类，可以通过比较器电路值问题将其减少一个对数空间，我们知道NLOG？ CC？ P. Cook等。 （2014年）表明CC也是由多项式大小比较器电路系列决定的语言类别。我们研究比较器电路模型的概括，该模型适用于固定的有限有界坐姿。我们观察到，甚至在任意固定的有限有界坐姿上也存在通用比较器电路。在此基础上，我们显示以下内容：-固定有限分布格上具有多项式大小的比较器电路代表CC类。当电路被限制为偏斜时，它们表征LOG。注意到（均匀）多项式大小的布尔电路（对应偏斜）表征了P（对应NLOG），这表明在P vs CC和NLOG vs LOG问题之间进行了比较。 -补充这一点，我们表明即使在比较器电路偏斜的情况下，在任意固定的有限格子上具有多项式大小的比较器电路也具有P类特征。 -另外，我们通过固定有限有界坐姿上的多项式大小比较器电路族显示了NP类的特征。顺便说一句，我们考虑布尔公式在任意晶格上的推广。我们证明了Spira定理（1971）也可以扩展到该设置，并且表明有限固定格上的多项式大小的布尔公式捕获了NC ^ 1类。这些结果概括了Cook等人的结果。等（2014年）关于比较器电路的电源。我们的技术涉及比较器电路和有限姿态的设计。然后，我们使用晶格理论中的已知结果表明，我们获得的姿势可以嵌入适当的晶格中。我们的结果为建立问题的CC上限提供了新的方法，并指出了使用晶格理论方法针对问题P vs CC和NLOG vs LOG的潜在新方法。对先前版本的更改：在早期版本中，我们错误地声称，晶格上的多尺寸偏斜比较器电路族实际上是NL的特征，而NL则是NL的特征。
展开▼
