论文标题
一般后分复发和多项式时间完整性
General Ramified Recurrence and Polynomial-time Completeness
论文作者
论文摘要
我们表现出声音和完整的隐式复杂性形式主义，可用于通过归纳定义的数据结构而通过结构递归计算的功能。可行的可计算在这里意味着结构复发定义在时间多项式上以输入表示这些表示形式使用数据共享的表示。归纳定义的数据结构包括列表和树。此处的健全意味着隐性复杂性形式主义中的程序具有可行的运行时间。这里的完整性意味着可行的结构递归计算得出的每个函数都具有隐性复杂性形式主义的程序。本文是对Avanzini，Dal Lago，Martini和Zorzi的工作的后续作品，他们专注于这种形式主义的健全性，但并未考虑完整性的问题。
We exhibit a sound and complete implicit-complexity formalism for functions feasibly computable by structural recursions over inductively defined data structures. Feasibly computable here means that the structural-recursive definition runs in time polynomial in the size of the representation of the inputs where these representations may make use of data sharing. Inductively defined data structures here includes lists and trees. Soundness here means that the programs within the implicit-complexity formalism have feasible run times. Completeness here means that each function computed by a feasible structural recursion has a program in the implicit-complexity formalism. This paper is a follow up on the work of Avanzini, Dal Lago, Martini, and Zorzi who focused on the soundness of such formalisms but did not consider the question of completeness.
