新递归理论特征：无需边界限制的多项式时间计算

本文探讨了一个新的递归理论特征，旨在描述多项式时间计算，使其独立于任何预设的资源限制。Cobham的多时函数理论是一个经典概念，它通过包含特定的初始函数并在复合和有界递归运算下封闭来刻画多时间函数。然而，Cobham的刻画存在局限性，特别是在处理递归运算时，它依赖于明确的大小界限，如函数输出长度不超过2|X|·|y|。 Leivant的贡献在于他提出了一种更优雅的刻画方式，即函数是多项式时间的当且仅当它可以通过逻辑系统L2（QF+）中的递归方程和满射原则证明收敛。这个系统允许使用字符串后继函数，但无需显式大小限制，从而避免了对增长率的依赖。Leivant的结果暗示了可能通过某种方式去除增长控制，使递归理论更加灵活。 本文作者试图建立一个与增长率界限脱钩的递归理论表征，其核心是符号上的组合和递归，所有的初始函数都是相对小型的，其输出不会超过字符串后继函数。这种方法挑战了传统的递归理论框架，并引出一个疑问：在不依赖于逻辑和可预测性的条件下，如何进一步发展递归类型的理论。 相比之下，Immerman等人在有限模型理论中尝试无资源地表征多时间关系，但通常局限于关系而非函数。这与本文关注的焦点有所不同，因为后者专注于函数的递归性质和无界复杂性分析。 本文通过对递归理论的创新性解读，提供了多项式时间计算的新视角，强调了在资源限制之外寻找更为通用和灵活的理论框架的重要性。通过避免硬编码的增长条件，作者的工作可能为计算复杂性理论开辟新的研究方向。