Isolation, matching, and counting uniform and nonuniform upper bounds

We show that the perfect matching problem is in the complexity class SPL (i n the nonuniform setting). This provides a better upper bound on the comple xity of the matching problem, as well as providing motivation For studying the complexity class SPL. Using similar techniques, we show that counting t he number of accepting paths of a nondeterministic logspace machine can be done in NL/poly, if the number of paths is small. This clarifies the comple xity of the class FewL. Using derandomization techniques, we then improve t his to show that this counting problem is in NL. Determining if our other t heorems hold in the uniform setting remains an important open question, alt hough we provide evidence that they do. More precisely, if there are proble ms in DSPACE(n) requiring exponential-size circuits, then all of our result s hold in the uniform setting. (C) 1999 Academic Press.