Abstract

Motivated by results on interactive proof systems we investigate an ∃-∀hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every class of this hierarchy coincides with one of the following Classes: ∑math image, Πmath image , PSPACE, ∑math image or Πmath image . This improves previous results by Orponen [6] and allows interesting comparisons with the above mentioned results on inter-active proof systems