The complexity of the comparator circuit value problem

DOI10.1145/2635822MaRDI QIDQ2828221zbMATH OpenOpenAlexFDO

Authors Yuval Filmus, Dai Tri Man Lê, Stephen Cook

Publication date 24 October 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

P-completenesscomparator circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: In 1990 Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL subseteq CC subseteq P, and proved that in addition to CCV several other problems are complete for CC, including the stable marriage problem, and finding the lexicographically first maximal matching in a bipartite graph. We are interested in CC because we conjecture that it is incomparable with the parallel class NC which also satisfies NL subseteq NC subseteq P, and note that this conjecture implies that none of the CC-complete problems has an efficient polylog time parallel algorithm. We provide evidence for our conjecture by giving oracle settings in which relativized CC and relativized NC are incomparable. We give several alternative definitions of CC, including (among others) the class of problems computed by uniform polynomial-size families of comparator circuits supplied with copies of the input and its negation, the class of problems AC^0-reducible to CCV, and the class of problems computed by uniform AC^0 circuits with CCV gates. We also give a machine model for CC, which corresponds to its characterization as log-space uniform polynomial-size families of comparator circuits. These various characterizations show that CC is a robust class. The main technical tool we employ is universal comparator circuits. Other results include a simpler proof of NL subseteq CC, and an explanation of the relation between the Gale-Shapley algorithm and Subramanian's algorithm for stable marriage. This paper continues the previous work of Cook, L^e and Ye which focused on Cook-Nguyen style uniform proof complexity, answering several open questions raised in that paper.

Recommendations

• A formal theory for the complexity class associated with the stable marriage problem
• The complexity of circuit value and network stability
• scientific article; zbMATH DE number 512869

Cites work

• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• A New Approach to Stable Matching Problems
• A fast parallel algorithm for the maximal independent set problem
• A formal theory for the complexity class associated with the stable marriage problem
• A new fixed point approach for stable networks and stable marriages
• A taxonomy of problems with fast parallel algorithms
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem
• College Admissions and the Stability of Marriage
• Constructing a perfect matching is in random NC
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• Logical Foundations of Proof Complexity
• Matching is as easy as matrix inversion
• On uniformity within \(NC^ 1\)
• Stable networks and product graphs
• The complexity of circuit value and network stability

Cited in

(3)

• scientific article; zbMATH DE number 4008288 (Why is no real title available?)
• Adventures in monotone complexity and TFNP
• Algorithms and lower bounds for comparator circuits from shrinkage

This page was built for publication: The complexity of the comparator circuit value problem

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