paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Bounded time computation on metric spaces and Banach spaces

度量空间与 Banach 空间上的有界时间计算
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 论文研究度量空间与 Banach 空间上算子的有界时间计算复杂度，属于二阶复杂度理论与可计算分析，与用户关注的静态分析、Agentic 程序、浮点程序分析以及 LLM 交叉均无直接关联。引用 8 inbox
Matthias Schroder, Florian Steinberg
逻辑与自动机
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话：将二阶复杂度理论经表示提升到度量空间与 Banach 空间，扩展分析中算子的有界时间计算框架。

本文扩展了 Kawamura 与 Cook 提出的分析中算子计算复杂度框架，研究度量空间与 Banach 空间上的有界时间计算。其方法以 Baire 空间上泛函的二阶复杂度理论为基础，通过表示（representation）将计算问题提升到度量空间，并用输入编码长度与输出精度来度量时间。该工作为分析中的算子提供了一种统一的复杂度语义，使有界时间计算可覆盖更一般的度量与 Banach 空间结构，并为后续可计算分析中的复杂度研究奠定模型基础。

问题
如何为分析中的算子建立有界时间计算与复杂度模型，并将其从 Baire 空间推广到度量空间和 Banach 空间。
方法
以 Baire 空间上泛函的二阶复杂度理论为基础，通过表示（representation）把计算复杂度提升到度量空间，并以输入编码长度和输出精度作为时间度量。
评估
通过理论扩展与形式化论证评估模型，继承 Kawamura-Cook 框架并说明其在度量空间与 Banach 空间上的适用性。
原文摘要（Abstract）

We extend Kawamura and Cook's framework for computational complexity for operators in analysis. This model is based on second-order complexity theory for functionals on the Baire space, which is lifted to metric spaces via representations. Time is measured in the length of the input encodings and the output precision.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@inproceedings{SchroderS17,
  title = {Bounded time computation on metric spaces and Banach spaces},
  author = {Matthias Schroder and Florian Steinberg},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005139}
}