A Foundational Delineation of Poly-time
A Foundational Delineation of Poly-time
复制标题
多时间的基本描述
DOI：
--
复制
发表时间：
1994
影响因子：
1
通讯作者：
D. Leivant
中科院分区：
文献类型：
--
作者：
D. Leivant
我们证明了一个在{0，1}* 上的函数是多时间的当且仅当它是由一个方程程序计算的，该方程程序可以被证明在构造性二阶逻辑中处处收敛，其中集合存在（理解）限制于正的无量词公式，或者对于正的存在公式具有集合存在。这些集合存在原则传达了一种无限集合的本体论，它是进化的，而不是完成的，整体。因此，我们的表征结果可以被视为一个基本的理由，确定多时间的可行性。
We show that a function over {0, 1}* is poly-time iff it is computed by an equational program which can be proved to be everywhere converging in constructive second-order logic with set-existence (comprehension) restricted to positive quantifier-free formulas, or alternatively with set-existence for positive existential formulas. These set-existence principles convey an ontology of infinite sets as evolving, not completed, totalities. Our characterization results can consequently be viewed as a foundational justification for identifying poly-time with feasibility.