A note on parallel and alternating time (Q2465291): Difference between revisions

Denote by \(\text{PSPACE}_{\mathbb R}\) the class of sets of real vectors decidable in exponential time and using polynomial space; by \(\text{PAT}_{\mathbb R}\) the class of sets decidable using polynomial alternating time; and by \(\text{PAR}_{\mathbb R}\) the one of those decidable using parallel polynomial time. The goal of this paper is to investigate the boundaries between these notions by looking at quantifiers with a restricted expressive power and considering the classes they define. More precisely, the studied quantifiers are the digital quantifiers for which the above classes are naturally modified. The first main result is that \(\text{DPAT}_{\mathbb R}^{\text{PH}_{\mathbb R}}\subseteq \text{PAR}_{\mathbb R}\), where \(\text{DPAT}_{\mathbb R}\) is the class of digital polynomial alternating time and \(\text{PH}_{\mathbb R}\) denotes the polynomial hierarchy over the reals. The second main result is that \(\text{PAR}_{\mathbb R}\subseteq \text{MA}\forall_{\mathbb R}\) and \(\text{PAR}_{\mathbb R}\subseteq \text{MA}\exists_{\mathbb R}\), where \(\text{MA}\exists_{\mathbb R}\) denotes the class containing all sets decidable alternation digital universal and real existential guesses in polynomial time. Similarly \(\text{MA}\forall_{\mathbb R}\) denotes the class contains all sets decidable alternating digital existential and real guesses in polynomial time.