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 ... more >>>

We show that in the context of nonuniform complexity,
nondeterministic logarithmic space bounded computation can be made
unambiguous. An analogous result holds for the class of problems
reducible to context-free languages. In terms of complexity classes,
this can be stated as:
NL/poly = UL/poly
LogCFL/poly ... more >>>