Recently, the property of unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally-unique games by Aida et al. and in the design of efficient protocols involving globally-unique games by Crasmaru et al.. This paper investigates the power of unambiguity in alternating Turing machines in the following settings: 1. We construct a relativized world where unambiguity based hierarchies—AUPH, UPH, and UPH—are infinite. We construct another relativized world where UAP (unambiguous alternating polynomial-time) is not contained in the polynomial hierarchy. 2. We define the bounded-level unambiguous alternating solution class UAS(k), for every k ≥ 1, as the class of sets for which strings in the set are accepted unambiguously by some polynomial-time alternating Turing machine N with at most k alternations, while strings not in the set either are rejected or are accepted with ambiguity by N. We construct a relativized world where, for all k ≥ 1, UP_( ≤ k) is contained in UP_( ≤ k+1) and UAS(k) is contained in UAS(k+1). 3. Finally, we show that robustly k-level unambiguous polynomial-time alternating Turing machines accept languages that are computable in p~(∑_k~p?A) for every oracle A. This generalizes a result of Hartmanis and Hemachandra.
展开▼
