11.00 a.m.
How powerful is logspace unambiguity?
Ragunath Tewari
IIT Kharagpur.
11-11-11

---

Abstract

The fundamental question in the area of logarithmic space unambiguity is whether unambiguity captures non-determinism in the logspace domain. Although we do not yet have answer to this question, but certain results give evidence that probably the answer to the former question is positive. ReachUL is an unambiguous class of languages such that any computation has at most one path from the start configuration to any other configuration. On the other hand, ReachFewL is a the class of languages such that any computation has at most polynomially many paths from the start configuration to any other configuration. We show that ReachUL = ReachFewL.

We also show that reachability in planar graphs can be decided in unambiguous logspace using a celebrated result from multivariable calculus, known as Green's Theorem.