A foundational delineation of computational feasibility
A foundational delineation of computational feasibility
复制标题
计算可行性的基本描述
DOI：
10.1109/lics.1991.151625
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
D. Leivant
中科院分区：
文献类型：
--
作者：
D. Leivant
提出了一个与可行性直接相关的原理，证明了用可行计算来识别P-时间的合理性。它表明，可计算的功能证明的基础上积极的量词自由理解正是在确定性多项式时间可计算的功能。这表明P-时间类自然地产生于可行性的基础分析，并且只有在承认无限集合是完全的总体的情况下，使用幂运算的术语才有意义。<<ETX>>
A principle directly pertinent to feasibility, which justifies the identification of P-time with feasible computing, is proposed. It is shown that the computable functions justified on the basis of positive quantifier-free comprehension are precisely the functions computable in deterministic polynomial time. This shows that the class P-time arises naturally from a foundational analysis of feasibility, and that terms using exponentiation can be justified as meaningful only under the admission of infinite sets as completed totalities.<<ETX>>