𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A time-space hierarchy between polynomial time and polynomial space

✍ Scribed by P. Clote

Publisher
Springer
Year
1992
Tongue
English
Weight
808 KB
Volume
25
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

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