A framework for representing and solving NP search problems
David G. M. Mitchell, Eugenia Ternovska · 2005
NP search and decision problems occur widely in AI, and a number of general-purpose methods for solving them have been developed. The dominant approaches include propo-sitional satisfiability (SAT), constraint satisfaction problems (CSP), and answer set programming (ASP). Here, we propose a declarative constraint programming framework which we believe combines many strengths of these approaches, while addressing weaknesses in each of them. We formalize our ap-proach as a model extension problem, which is based on the classical notion of extension of a structure by new relations. A parameterized version of this problem captures NP. We dis-cuss properties of the formal framework intended to support effective modelling, and prospects for effective solver design.