Klaus Reinhardt, Eric Allender

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

Joshua Cook

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>