๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parity, circuits, and the polynomial-time hierarchy

โœ Scribed by Merrick Furst; James B. Saxe; Michael Sipser

Publisher
Springer
Year
1984
Tongue
English
Weight
880 KB
Volume
17
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

๐Ÿ“œ 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

On the power of parity polynomial time
On the power of parity polynomial time
โœ Jin-yi Cai; Lane A. Hemachandra ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Springer ๐ŸŒ English โš– 794 KB
Bounding queries in the analytic polynom
Bounding queries in the analytic polynomial-time hierarchy
โœ Herbert Baier; Klaus W. Wagner ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 1004 KB

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

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