Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-019 | 5th April 1998 00:00

Isolation, Matching, and Counting

RSS-Feed




TR98-019
Authors: Eric Allender, Klaus Reinhardt
Publication: 6th April 1998 09:34
Downloads: 1065
Keywords: 


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.



ISSN 1433-8092 | Imprint