一句话：提出可定义 while 程序，刻画遗传可定义集合上的可计算函数，并定义固定维多项式时间复杂性类。
论文研究在可能无限的遗传可定义集合上如何定义可计算性与易处理性。这类集合基于固定底层逻辑结构（如 (N,=)）定义。作者提出可定义 while 程序，并证明在底层结构满足适当假设时，它恰好刻画该类集合上的可计算函数。随后引入固定维多项式时间复杂性类，用以描述遗传可定义集合上的多项式时间计算，并证明它包含在合适资源界下可定义 while 程序所计算的函数。若反向包含成立，则将证明带计数的无选择多项式时间（Choiceless Polynomial Time with Counting）捕获有限图上的多项式时间。
We propose a definition for computable functions on hereditarily definable sets. Such sets are possibly infinite data structures that can be defined using a fixed underlying logical structure, such as (N, =). We show that, under suitable assumptions on the underlying structure, a programming language called definable while programs captures exactly the computable functions. Next, we introduce a complexity class called fixed-dimension polynomial time, which intuitively speaking describes polynomial computation on hereditarily definable sets. We show that this complexity class contains all functions computed by definable while programs with suitably defined resource bounds. Proving the converse inclusion would prove that Choiceless Polynomial Time with Counting captures polynomial time on finite graphs.
DOI 原文 ·
@inproceedings{paperbot4368,
title = {On computability and tractability for infinite sets},
author = {Mikołaj Bojańczyk and Szymon Toruńczyk},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209190}
}