• DocumentCode
    2142671
  • Title

    Isolation, matching, and counting

  • Author

    Allender, Eric ; Reinhardt, Klaus

  • Author_Institution
    Dept. of Comput. Eng., Rutgers Univ., Piscataway, NJ, USA
  • fYear
    1998
  • fDate
    15-18 Jun 1998
  • Firstpage
    92
  • Lastpage
    100
  • Abstract
    We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting
  • Keywords
    computational complexity; complexity class LogFew; complexity class SPL; counting; isolation; matching; nonuniform setting; perfect matching problem; upper bound; Computer science; Polynomials; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on
  • Conference_Location
    Buffalo, NY
  • ISSN
    1093-0159
  • Print_ISBN
    0-8186-8395-3
  • Type

    conf

  • DOI
    10.1109/CCC.1998.694594
  • Filename
    694594
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2142671