On Reformulation of Constraint Satisfaction Problems (Extended Version)

The performance of constraint based problem solving depends crucially on the problem representation. The same problem may be easy or difficult to solve depending on the way we formulate it. In this paper, we study reformulations of discrete constraint satisfaction problems (CSPs). We present a technique to transform a CSP P into its Boolean form, which allows us to find different reformulations of P . We identify a new class of tractable CSPs and present sufficient conditions for detecting solvability and unsolvability of a CSP in linear time. Finally we introduce the notion of fault tolerance of solutions, and show how the Boolean form can be used to find them. Keywords: Constraint-Based Reasoning 1 Introduction Performance of problem solving depends crucially on the problem representation. The same problem may be easy or difficult to solve depending on the way we describe it. Recently, the problem of obtaining and comparing different problem encodings was raised as an AI challeng..