Unambiguous Functions in Logarithmic Space

Abstract

<p> The notion of nondeterminism is one of the most fundamental concepts in many areas of computer science. Unambiguity, requiring that there be at most one correct sequence of nondeterministic choices, has proved to be one of the most meaningful restrictions of nondeterminism. In the context of space-bounded Turing Machines, several variants of unambiguity have been proposed and studied, and some interesting results have been established, narrowing slightly the gap between deterministic and nondeterministic logarithmic-space computation.</p> <p> We study the different variants of unambiguity in the context of computing multi-valued functions (as opposed to the usual yes/no decision problems). We propose a modification to the standard computation models of Turing Machines and configuration graphs, which allows for unambiguity-preserving composition. We introduce a unified notation, capturing the different flavors of ambiguity. Furthermore, we define a notion of reductions (based on function composition), which allows non-determinism but controls its level of ambiguity. In the light of this framework we establish some reductions between different variants of path counting problems. We also investigate more carefully the technique of inductive counting, and obtain improvement of some existing results.</p>