The Analytic Polynomial‐Time Hierarchy
Herbert Baier, Klaus W. Wagner · Mathematical logic quarterly · 1998
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 (arithmetic) 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: ∑ , Π (k⩾0), PSPACE, ∑ or Π (k⩾1). This improves previous results by Orponen [6] and allows interesting comparisons with the above mentioned results on inter‐active proof systems.