期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
