序列关系关系分解 (Sequential Relational Decomposition)

from arxiv, An extended abstract of this article appeared in the Proceedings of the 33rd Annual {ACM/IEEE} Symposium on Logic in Computer Science, {LICS} 2018

The concept of decomposition in computer science and engineering is considered a fundamental component of computational thinking and is prevalent in design of algorithms, software construction, hardware design, and more. We propose a simple and natural formalization of sequential decomposition, in which a task is decomposed into two sequential sub-tasks, with the first sub-task to be executed out before the second sub-task is executed. These tasks are specified by means of input/output relations. We define and study decomposition problems, which is to decide whether a given specification can be sequentially decomposed. Our main result is that decomposition itself is a difficult computational problem. More specifically, we study decomposition problems in three settings: where the input task is specified explicitly, by means of Boolean circuits, and by means of automatic relations. We show that in the first setting decomposition is NP-complete, in the second setting it is NEXPTIME-complete, and in the third setting there is evidence to suggest that it is undecidable. Our results indicate that the intuitive idea of decomposition as a system-design approach requires further investigation. In particular, we show that adding human to the loop by asking for a decomposition hint lowers the complexity of decomposition problems considerably.

翻译：计算机科学和工程的分解概念被视为计算思维的基本组成部分,在算法、软件制造、硬件设计的设计中很普遍。我们建议简单和自然地将顺序分解正规化,将任务分解成两个相继的子任务,在第二个子任务执行之前将执行第一个子任务。这些任务通过输入/输出关系具体化。我们定义和研究分解问题,即确定某一规格是否可以按顺序分解。我们的主要结果是分解本身是一个困难的计算问题。更具体地说,我们研究三个环境的分解问题:在明确指定输入任务的地方,通过布林电路和自动关系手段。我们表明,在第一个分解设置时,NP是完成的,在第二个设置是国家执行/产出关系中是完成的,在第三个设置中,有证据表明它是否可以按顺序分解。我们的结果表明,分解的分解概念本身是一个困难的计算问题。我们研究的三个环境:在三个环境中,通过布林电路路和自动关系的方式,明确指定了输入任务。我们表明,通过一个相当复杂的系统分解变的方法,我们需要相当复杂的分解的系统。