The complexity of the comparator circuit value problem

DOI10.1145/2635822zbMATH Open1347.68156arXiv1208.2721OpenAlexW2016263640MaRDI QIDQ2828221FDOQ2828221

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)

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)