𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounding queries in the analytic polynomial-time hierarchy

✍ Scribed by Herbert Baier; Klaus W. Wagner

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
1004 KB
Volume
207
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

In a previous paper the present authors (Baier and Wagner, 1996) investigated an S-V-hierarchy over P using word quantifiers as well as two types of set quantifiers, the so-called analytic polynomial-time hierarchy. The fact that some constructions there result in a bounded number of oracle queries and the recent PCP results which can be expressed by set quantifiers with a bounded number of queries motivated us to examine a hierarchy which extends the analytic polynomial-time hierarchy by considering restrictions on the number of oracle queries. This hierarchy is called bounded anulytic polynomial-time hierarchy. We show that every class from this hierarchy having a certain normal form coincides with one of the classes NP, coNP, PSPACE, Cy or II?

(k> 1). All these characterizations remain valid if the queries are asked in a nonadaptive form, i.e. in "parallel".

πŸ“œ SIMILAR VOLUMES

The Analytic Polynomial-Time Hierarchy
The Analytic Polynomial-Time Hierarchy
✍ Herbert Baier; Klaus W. Wagner πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 863 KB

Motivated by results on interactive proof systems we investigate an 3-V-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

The polynomial and linear time hierarchi
The polynomial and linear time hierarchies in V0
✍ Leszek A. KoΕ‚odziejczyk; Neil Thapen πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 203 KB

## Abstract We show that the bounded arithmetic theory V^0^ does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some au