BOUNDING QUERIES IN THE ANALYTIC POLYNOMIAL-TIME HIERARCHY

In a previous paper the present authors (Baier and Wagner, 1996) inves tigated an There Exists-For All-hierarchy over P using word quantifier s as well as two types of set quantifiers, the so-called analytic poly nomial-time hierarchy. The fact that some constructions there result i n a bounded number of oracle queries and the recent PCP results which can be expressed by set quantifiers with a bounded number of queries m otivated us to examine a hierarchy which extends the analytic polynomi al-time hierarchy by considering restrictions on the number of oracle queries. This hierarchy is called bounded analytic polynomial-time hie rarchy. We show that every class from this hierarchy having a certain normal form coincides with one of the classes NP, coNP, PSPACE, Sigma( k)(exp) Or Pi(k)(exp) (k greater than or equal to 1). All these charac terizations remain valid if the queries are asked in a nonadaptive for m, i.e, in ''parallel''. (C) 1998-Elsevier Science B.V. All rights res erved.