Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds

摘要

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 counting the 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 complexity of the class FewL. Using derandomization techniques, we then improve this to show that this counting problem is in NL. Determining if our other theorems hold in the uniform setting remains an important open question, although we provide evidence that they do. More precisely, if there are problems in DSPACE(n) requiring exponential-size circuits, then all of our results hold in the uniform setting.