A note on parallel and alternating time
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.
- Alternating time versus deterministic time: A separation
- A note on time operators
- A note on a time reversal problem
- A NOTE ON THE QUANTUM OF TIME
- scientific article; zbMATH DE number 5234028
- Remarks on the compatibility of opposite arrows of time
- Applications of time parallelization
- An algebraic theory of multiple clocks
- scientific article; zbMATH DE number 4114603 (Why is no real title available?)
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On digital nondeterminism
- On Relating Time and Space to Size and Depth
- On the complexity of quadratic programming in real number models of computation
- On the Complexity of Quantifier Elimination: the Structural Approach
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
This page was built for publication: A note on parallel and alternating time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465291)
