Derrick Stolee - Iowa State University - Research Browser

Unambiguity in log-space complexity classes
Problem and Results Summary

It is common in space-bounded computational complexity to consider the configuration graph of a computation. Deterministic machines produce configuration graphs where every vertex has out-degree 1. Non-deterministic machines produce configuration graphs with higher out-degree, but there is a path from the initial configuration to an accepting configuration if and only if the input is in the accepting language.

If we instead restrict that a non-deterministic machine has certain restrictions on the number of paths between certain types of nodes, then we are discussing unambiguous or few classes. For instance, UL is the class of languages decidable by nondeterministic log-space machines whose configuration classes have at most one accepting path. The class FewL is similar, except that the number of paths is bounded by some polynomial on the input size (as opposed to the possibly exponential number of paths in a typical NL machine).

The classes ReachUL and ReachFewL are defined to be the unambiguous and few classes where a nondeterministic log-space machine decides a language but the path count restrictions are from the initial configuration to any other configuration. The paper ReachFewL $=$ ReachUL has its main theorem as its title, showing two classes equal over 20 years after they were defined.

Research Papers
B. Garvin, D. Stolee, R. Tewari, N. V. Vinodchandran, ReachFewL $=$ ReachUL, Computational Complexity 23(1) (2014), pp 85-98.
Web Version Official Version
Support

Brady Garvin was supported by NSF grant CFDA#47.076 and AFOSR grant FA9550-10-1-0406. Derrick Stolee was supported by NSF grants CCF-0916525 and DMS-0914815. Raghunath Tewari and N. V. Vinodchandran were supported by NSF grant CCF-0916525.

Related Work
N. V. Vinodchandran, Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs, Electronic Colloquium on Computational Complexity TR14-008 (2014).
Presentations
B. Garvin, D. Stolee, R. Tewari, N. V. Vinodchandran, ReachFewL $=$ ReachUL, presented at COCOON 2011.
Slides

Derrick Stolee - Iowa State University - Research Browser