2026-08-16T16:53:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3244 2024-03-06T10:34:00Z ddc:004 open_access

A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem Lê, Dai Tri Man Cook, Stephen A. Ye, Yuli bounded arithmetic complexity theory comparator circuits Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem. He proved that several other problems are complete for CC, including the stable marriage problem, and finding the lexicographical first maximal matching in a bipartite graph. We suggest alternative definitions of CC based on different reducibilities and introduce a two-sorted theory VCC* based on one of them. We sharpen and simplify Subramanian's completeness proofs for the above two problems and formalize them in VCC*. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dai Tri Man Lê and Stephen A. Cook and Yuli Ye 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.381 urn:nbn:de:0030-drops-32440 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.381 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode