## Sequential relational decomposition

*Dror Fried*, *Axel Legay*,
*Joël
Ouaknine*, and *Moshe Y. Vardi*
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.

*Proceedings of LICS 18*, 2018. 10 pages.

PDF
© 2018 Association for Computing Machinery.

Imprint / Data Protection