__ Article:__

** Samuel R. Buss.
"The Polynomial Hierarchy and Intuitionistic Bounded
Arithmetic."
In **

** Download article: searchable
PDF or plain PDF. **

__Abstract__ Intuitionistic theories IS_{2}^{i}
of Bounded Arithmetic are introduced and it is shown that the definable
functions of IS_{2}^{i} are precisely the FP_{i}^{p}
functions of the polynomial time hierarchy. This is an extension of
earlier work on the classical Bounded Arithmetic and was first conjectured by
S. Cook. In contrast to the classical theories of Bounded Arithmetic
where Σ_{i}^{b}-definable functions are of interest, our
results for intuitionistic theories concern all the definable functions.

The method of proof uses FP_{i}^{p}-realizability
which is inspired by the recursive realizability of S.C. Kleene and D.
Nelson. It also involves the polynomial hierarchy functionals of finite
type which are introduced in this paper.