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 (defined and studied in [Buntrock, Damm, Hertrampf, Meinel] coincides with NL in the nonuniform setting. Finally, we also provide evidence that our results also hold in the uniform setting.