文章基本信息

标题：A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem
本地全文：下载
作者：Dai Tri Man Lê ; Stephen A. Cook ; Yuli Ye 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：12
页码：381-395
DOI：10.4230/LIPIcs.CSL.2011.381
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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*.
关键词：bounded arithmetic; complexity theory; comparator circuits