Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00037-009-0264-6 | Computational Complexity |
Keywords | Field | DocType |
parallel polynomial time,complexity classes,. quantifier prefixes,real version,real universal quantifiers,real existential quantifiers,parallel time.,quantifier prefixes,alternation,boolean quantifiers,parallel time,polynomial time,complexity class | Complexity class,Discrete mathematics,Combinatorics,Polynomial,Prefix,Time complexity,Mathematics,Alternation (linguistics) | Journal |
Volume | Issue | ISSN |
18 | 4 | 1420-8954 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Felipe Cucker | 1 | 666 | 68.99 |
| Paulin Jacobé de Naurois | 2 | 34 | 4.98 |