Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Klaus Reinhardt:

TR98-019 | 5th April 1998
Eric Allender, Klaus Reinhardt

Isolation, Matching, and Counting

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

TR97-014 | 25th April 1997
Klaus Reinhardt, Eric Allender

Making Nondeterminism Unambiguous

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

ISSN 1433-8092 | Imprint