Parallel Time and Quantifier Prefixes |
| |
Authors: | Felipe Cucker Paulin Jacobé de Naurois |
| |
Affiliation: | 1. Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong 2. CNRS UMR 7030 – LIPN, Université Paris 13, 99 av. J.B. Clement, 93430, Villetaneuse cedex, France
|
| |
Abstract: | We characterize the amount of alternation between blocks of Boolean quantifiers (having both existential and universal), blocks of real existential quantifiers, and blocks of real universal quantifiers that can be decided in parallel polynomial time over the reals. We do so under the assumption that blocks have a uniform bound on their size, both for the case of this bound to be polynomial and constant. On the way towards this characterization we prove a real version of Savitch’s Theorem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|