Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-014 | 25th April 1997 00:00

Making Nondeterminism Unambiguous

RSS-Feed




TR97-014
Authors: Klaus Reinhardt, Eric Allender
Publication: 25th April 1997 13:58
Downloads: 2209
Keywords: 


Abstract:

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 = UAuxPDA(log n, polynomial)/poly



ISSN 1433-8092 | Imprint