𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Relating the bounded arithmetic and polynomial time hierarchies

✍ Scribed by Samuel R. Buss

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
711 KB
Volume
75
Category
Article
ISSN
0168-0072

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

Polynomial induction and length minimiza
Polynomial induction and length minimization in intuitionistic bounded arithmetic
✍ Morteza Moniri πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 80 KB

## Abstract It is shown that the feasibly constructive arithmetic theory IPV does not prove (double negation of) LMIN(NP), unless the polynomial hierarchy CPV‐provably collapses. It is proved that PV plus (double negation of) LMIN(NP) intuitionistically proves PIND(coNP). It is observed that PV + P

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