𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Analytic Polynomial-Time Hierarchy

✍ Scribed by Herbert Baier; Klaus W. Wagner

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
863 KB
Volume
44
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 class of this hierarchy coincides with one of the following Classes: El;, II; (k 2 O ) , PSPACE, C y p or IIyp (k 2 1). This improves previous results by Orponen [6] and allows interesting comparisons with the above mentioned results on interactive proof systems.

πŸ“œ SIMILAR VOLUMES

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

The extended Analytic Hierarchy Decision
The extended Analytic Hierarchy Decision method
✍ Joseph M. Lambert πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 833 KB

This paper extends the Analytic Hierarchy Decision Model of T.L. Saaty by enlarging the set of pairwise comparison values to allow indecision or noncomparability between two alternatives.