An Algebraic Approach to Constraint Satisfaction Problems
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Search. Pages 284-288.
Abstract
A constraint satisfaction problem, or CSP, can be reformulated as an integer linear programming problem. The reformulated problem can be solved via polynomial multiplication. If the CSP has n variables whose domain size is m, and if the equivalent programming problem involves M equations, then the number of solutions can be determined in time O(nm2M-n). This surprising link between search problems and algebraic techniques allows us to show improved bounds for several constraint satisfaction problems, including new simply exponential bounds for determining the number of solutions to the n-queens problem. We also address the problem of minimizing M for a particular CSP.
@inproceedings{ijcai1989p45,
title = {An Algebraic Approach to Constraint Satisfaction Problems},
author = {Rivin, Igor and Zabih, Ramin},
booktitle = {Proceedings of the Eleventh International Joint Conference on
Artificial Intelligence, {IJCAI-89}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {N. S. Sridharan},
pages = {284--288},
year = {1989},
month = {8},
note = {Search},
url = {https://ijcai.org/proceedings/1989/45},
}
TY - CPAPER TI - An Algebraic Approach to Constraint Satisfaction Problems AU - Rivin, Igor AU - Zabih, Ramin T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 284 EP - 288 UR - https://ijcai.org/proceedings/1989/45 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
