97-46: Making Nondeterminism Unambiguous

DIMACS TR: 97-46

Making Nondeterminism Unambiguous

Authors: Klaus Reinhardt and Eric Allender

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, poly)/poly

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-46.ps.gz

DIMACS Home Page