Abstract:

Unambiguity in nondeterministic Turing machines is a well-studied
concept in structural complexity. It has proved to be useful in
characterizing worst-case one-to-one one-way functions, studying
closure of #P under polynomial-time computable operations,
classifying natural computational problems, and in the context
of propositional proof systems.

In this talk, we will first review the concept of unambiguity in
nondeterministic, alternating, and hierarchical models of
computation. Then we will demonstrate the power of unambiguity in
these computational models.

This talk is based on joint work with Holger Spakowski.