Computational Complexity of Multi-Way, Dataflow Constraint Problems
Abstract
Although it is widely acknowledged that multi-way dataflow constraints make it easier to specify certain relationships in interactive applications, concerns about their efficiency have impeded their acceptance. Some of the local propagation algorithms that solve these constraints are polynomial, others (such as SkyBlue) are exponential. In fact, every system handles a specific problem and the influence of any particular restriction on the computational complexity is not yet precisely determined. In this report, we present theoretical results that allow us to classify existing multiway constraint problems. We especially prove that the problem handled by SkyBlue is NP-hard.
Cite
Text
Trombettoni and Neveu. "Computational Complexity of Multi-Way, Dataflow Constraint Problems." International Joint Conference on Artificial Intelligence, 1997.Markdown
[Trombettoni and Neveu. "Computational Complexity of Multi-Way, Dataflow Constraint Problems." International Joint Conference on Artificial Intelligence, 1997.](https://mlanthology.org/ijcai/1997/trombettoni1997ijcai-computational/)BibTeX
@inproceedings{trombettoni1997ijcai-computational,
title = {{Computational Complexity of Multi-Way, Dataflow Constraint Problems}},
author = {Trombettoni, Gilles and Neveu, Bertrand},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1997},
pages = {358-365},
url = {https://mlanthology.org/ijcai/1997/trombettoni1997ijcai-computational/}
}