The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic
The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic
复制标题
多项式层次结构和直觉有界算术
DOI：
--
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
S. Buss
中科院分区：
文献类型：
--
作者：
S. Buss
介绍了有界算术的直觉理论IS 2 i，证明了IS 2 i的可定义函数正好是多项式族的-i p函数。这是早期关于经典有界算术的工作的扩展，最早是由S.Cook猜测的。与经典的有界算术理论中Σi b可定义函数不同，我们的直觉主义理论的结果涉及所有可定义函数。
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 □ i p functions of the polynomial 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.