paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Polynomial Time and Dependent Types

多项式时间与依赖类型
POPL 8(POPL)2024匹配度 2/10 · 该论文研究依赖类型、线性类型与定量类型论,用于保证程序的多项式时间计算复杂度,属于纯类型论与计算复杂度理论。它与用户核心关注的 PL 与 AI/LLM 交叉、Agentic 程序静态分析、浮点程序分析、贝叶斯程序分析等方向没有直接关联,仅在形式化验证和类型系统的理论背景上有非常弱的交集。引用 5 inbox
Robert Atkey
crossref: 2026-09-10

AI 速览

一句话:将依赖类型与线性类型系统结合,用定量类型论保证项的计算复杂度为多项式时间。

论文研究如何用类型系统同时表达依赖类型中的类型级任意计算与项级资源消耗,从而可靠且完备地刻画多项式时间计算。作者考察两种系统:一种禁止构造可迭代数据,另一种沿用 Hofmann 的 LFPL,通过“付费”机制控制数据构造。二者均借助定量类型论(Quantitative Type Theory)扩展到完整依赖类型。可靠性证明采用 Dal Lago 与 Hofmann 的 realizability 技术。长期目标是把类型论的外延推理与程序内在资源消耗的内涵推理结合,为资源分析工具和合成计算复杂度理论奠定基础。

问题
如何将依赖类型与线性类型结合,在类型级可进行任意计算的同时,保证项级程序在多项式时间内运行,并可靠且完备地刻画多项式时间。
方法
提出两种线性类型系统:一种禁止可迭代数据构造,另一种基于 LFPL 的付费机制控制构造;再通过定量类型论扩展到完整依赖类型。可靠性证明采用 Dal Lago 与 Hofmann 的 realizability 技术。
评估
评估以理论证明为主:证明系统可靠性,并论证其可靠且完备地刻画多项式时间;摘要未涉及实现或实验评估。
原文摘要(Abstract)

We combine dependent types with linear type systems that soundly and completely capture polynomial time computation. We explore two systems for capturing polynomial time: one system that disallows construction of iterable data, and one, based on the LFPL system of Martin Hofmann, that controls construction via a payment method. Both of these are extended to full dependent types via Quantitative Type Theory, allowing for arbitrary computation in types alongside guaranteed polynomial time computation in terms. We prove the soundness of the systems using a realisability technique due to Dal Lago and Hofmann. Our long-term goal is to combine the extensional reasoning of type theory with intensional reasoning about the resources intrinsically consumed by programs. This paper is a step along this path, which we hope will lead both to practical systems for reasoning about programs’ resource usage, and to theoretical use as a form of synthetic computational complexity theory .

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2643,
  title = {Polynomial Time and Dependent Types},
  author = {Robert Atkey},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {8},
  number = {POPL},
  year = {2024},
  doi = {10.1145/3632918}
}