AAAI Publications, Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence

Font Size: 
From Unsolvable to Solvable: An Exploration of Simple Changes
Susan L. Epstein, Xi Yun

Last modified: 2010-07-07

Abstract


This paper investigates how readily an unsolvable constraint satisfaction problem can be reformulated so that it becomes solvable. We investigate small changes in the definitions of the problemís constraints, changes that alter neither the structure of its constraint graph nor the tightness of its constraints. Our results show that structured and unstructured problems respond differently to such changes, as do easy and difficult problems taken from the same problem class. Several plausible explanations for this behavior are discussed.

Full Text: PDF