Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NONDETERMINISTIC SPACE:
Reports tagged with Nondeterministic space:
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