Computational Complexity of Multi-way, Dataflow Constraint Problems
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 358-364.
Abstract
Although it is acknowledged that multi-way dataflow constraints are useful in interactive applications, concerns about their tractability have hindered their acceptance. Certain local propagation algorithms that solve these constraints are polynomial, others (such as SkyBlue) are exponential. Every system handles a specific problem and the influence of any particular restriction on the computational complexity is not yet precisely determined. In this paper, we present three theoretical results that allow us to classify existing multi-way constraint problems. Especially, we prove that the problem handled by SkyBlue is NP-hard.
@inproceedings{ijcai1997p53,
title = {Computational Complexity of Multi-way, Dataflow Constraint Problems},
author = {Trombettoni, Gilles and Neveu, Bertrand},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {358--364},
year = {1997},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1997/53},
}
TY - CPAPER TI - Computational Complexity of Multi-way, Dataflow Constraint Problems AU - Trombettoni, Gilles AU - Neveu, Bertrand T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 358 EP - 364 UR - https://ijcai.org/proceedings/1997/53 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
