On the power of unambiguity in alternating machines

Unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally-unique games by Aida et al. [ACRW04] and in the design of efficient protocols involving globally-unique games by Crâsmaru et al. [CGRS04]. This paper explores the power of unambiguity in alternating Turing machines in the following settings: 1. We show that unambiguity based hierarchies—AUPH, UPH, and UPH—are infinite in some relativized world. For each k ≥ 2, we construct another relativized world where the unambiguity based hierarchies collapse so that they have exactly k distinct levels and their k’th levels coincide with PSPACE. These results shed light on the relativized power of the unambiguity based hierarchies, and parallel the results known for the case of the polynomial hierarchy. 2. For every k ≥ 1, we define the bounded-level unambiguous alternating solution class UAS(k) as the class of all sets L for which there exists a polynomial-time alternating Turing machine N, which need not be unambiguous on every input, with at most k alternations such that x ∈ L if and only if x is accepted unambiguously by N. We construct a relativized world where, for all k ≥ 1, UP≤k ⊂ UP≤k+1 and UAS(k) ⊂ UAS(k + 1)