License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.381
URN: urn:nbn:de:0030-drops-32440
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3244/
Go to the corresponding LIPIcs Volume Portal

Lê, Dai Tri Man ; Cook, Stephen A. ; Ye, Yuli

A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem

pdf-format:
31.pdf (0.6 MB)

Abstract

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*.

BibTeX - Entry

@InProceedings{l_et_al:LIPIcs:2011:3244,
  author =	{Dai Tri Man Lê and Stephen A. Cook and Yuli Ye},
  title =	{{A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{381--395},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3244},
  URN =		{urn:nbn:de:0030-drops-32440},
  doi =		{10.4230/LIPIcs.CSL.2011.381},
  annote =	{Keywords: bounded arithmetic, complexity theory, comparator circuits}
}

Keywords: bounded arithmetic, complexity theory, comparator circuits
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI