一句话：给出 N^d 有限集合在 majoring 与 minoring 序下受控坏序列长度的上下界，并转化为 fast-growing 复杂度类界。
论文研究有限 N^d 集合在 majoring 序与 minoring 序下受控坏序列（controlled bad sequences）的长度。作者用 Cichon 层级中的函数来刻画这些序列长度的增长，从而给出上界与下界。随后，这些结果被转换为 fast-growing 复杂度类中的界。因此，论文在序结构、Cichon 层级与快速增长的复杂度类之间建立了对应，为相关序列长度的复杂度提供了精细的上下界刻画。
We provide upper and lower bounds for the length of controlled bad sequences over the majoring and the minoring orderings of finite sets of Nd. The results are obtained by bounding the length of such sequences by functions from the Cichon hierarchy. This allows us to translate these results to bounds over the fast-growing complexity classes.
DOI 原文 ·
@inproceedings{paperbot5531,
title = {Complexity of controlled bad sequences over finite sets of Nd},
author = {A. R. Balasubramanian},
booktitle = {LICS},
year = {2020},
doi = {10.1145/3373718.3394753}
}