A Framework for Representing and Solving NP Search Problems

David G. Mitchell, Eugenia Ternovska

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 propositional 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 approach 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 discuss properties of the formal framework intended to support effective modelling, and prospects for effective solver design.

Content Area: 6. Constraint Satisfaction and Satisfiability

Subjects: 9.3 Mathematical Foundations; 9.2 Computational Complexity

Submitted: May 11, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.