Title :
Isolation, matching, and counting
Author :
Allender, Eric ; Reinhardt, Klaus
Author_Institution :
Dept. of Comput. Eng., Rutgers Univ., Piscataway, NJ, USA
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;
Conference_Titel :
Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on
Conference_Location :
Buffalo, NY
Print_ISBN :
0-8186-8395-3
DOI :
10.1109/CCC.1998.694594
