A note on parallel and alternating time

Felipe Cucker; Irénée Briquel

doi:10.1016/j.jco.2007.02.005

A note on parallel and alternating time

Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review

Overview

6 Scopus Citations

Scopus Metrics

View graph of relations

Author(s)

Felipe Cucker
Irénée Briquel

Related Research Unit(s)

Department of Mathematics

Detail(s)

Original language	English
Pages (from-to)	594-602
Journal / Publication	Journal of Complexity
Volume	23
Issue number	4-6
Publication status	Published - Aug 2007

Link(s)

DOI	DOI https://doi.org/10.1016/j.jco.2007.02.005 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-36249020902&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(7688a915-9e20-442b-9922-21b90944499e).html

Abstract

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.