论文标题
在线结构理论的基础II：操作员方法
Foundations of Online Structure Theory II: The Operator Approach
论文作者
论文摘要
我们介绍了在线结构理论的框架。我们的方法是在计算理论和复杂性理论的几个领域中独立产生的概念。我们建议使用操作员进行统一的方法，在该方法中，我们允许输入是任意复杂性的可计数对象。 We give a new framework which (i) ties online algorithms with computable analysis, (ii) shows how to use modifications of notions from computable analysis, such as Weihrauch reducibility, to analyse finite but uniform combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine structure of finite analogs of infinite combinatorial problems, and (iv) see how similar ideas can be amalgamated from诸如前学习，可计算分析，分布式计算等领域。关键的想法之一是，在线算法可以看作是可计算分析的子区域。相反，我们还从古典在线算法中获得了可计算分析的丰富。
We introduce a framework for online structure theory. Our approach generalises notions arising independently in several areas of computability theory and complexity theory. We suggest a unifying approach using operators where we allow the input to be a countable object of an arbitrary complexity. We give a new framework which (i) ties online algorithms with computable analysis, (ii) shows how to use modifications of notions from computable analysis, such as Weihrauch reducibility, to analyse finite but uniform combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine structure of finite analogs of infinite combinatorial problems, and (iv) see how similar ideas can be amalgamated from areas such as EX-learning, computable analysis, distributed computing and the like. One of the key ideas is that online algorithms can be viewed as a sub-area of computable analysis. Conversely, we also get an enrichment of computable analysis from classical online algorithms.
