A note on parallel and alternating time
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Related Research Unit(s)
|Journal / Publication||Journal of Complexity|
|Publication status||Published - Aug 2007|
|Link to Scopus||https://www.scopus.com/record/display.uri?eid=2-s2.0-36249020902&origin=recordpage|
A long standing open question in complexity theory over the reals is the relationship between parallel time and quantifier alternation. It is known that alternating digital quantifiers is weaker than parallel time, which in turn is weaker than alternating unrestricted (real) quantifiers. In this note we consider some complexity classes defined through alternation of mixed digital and unrestricted quantifiers in different patterns. We show that the class of sets decided in parallel polynomial time is sandwiched between two such classes for different patterns. © 2007 Elsevier Inc. All rights reserved.
- Alternation, Complexity classes, Parallelism