Abstract
This paper introduces a declarative framework for solving NP search problems based on the logical task of Model Extension (MX). By extending classical first-order logic with inductive definitions (FO(ID)), the authors provide a mathematically rigorous foundation that matches the expressive power of NP while offering a more intuitive modeling language than existing paradigms like SAT or Answer Set Programming (ASP). The framework bridges the gap between high-level modeling and efficient computation, providing a unified theory for various constraint-based solving techniques.
Introduction
In computer science and artificial intelligence, NP-complete problems—tasks where a solution is difficult to find but easy to verify—are ubiquitous. Applications range from hardware verification and scheduling to Sudoku and graph coloring. Currently, researchers typically approach these problems using one of three declarative paradigms:
- Satisfiability (SAT): Offers high-performance solvers but relies on a low-level propositional language that is difficult for humans to use for complex modeling.
- Constraint Satisfaction Problems (CSP): Provides better modeling primitives but often lacks a purely declarative, logic-based foundation.
- Answer Set Programming (ASP): Offers high expressive power and handles recursion well, but its "stable model" semantics can be non-intuitive and difficult to integrate with classical logical tools.
This research identifies a critical gap: the lack of a framework that combines the performance of SAT, the modeling ease of CSP, and the expressive power of ASP, all within the well-understood bounds of classical logic.
The Model Extension (MX) Framework
The authors propose Model Extension (MX) as the fundamental computational task for solving NP search problems. In the MX framework, a problem is defined by two components:
- The Problem Description: A logic formula $\phi$ that defines the constraints of the problem.
- The Instance: A partial structure $A_I$ (such as a specific graph or database) representing the input data.
The goal is to find an "extension" of the partial structure—filling in the missing relations—such that the resulting complete structure satisfies the formula $\phi$. This approach naturally separates the general rules of a problem from the specific data of an instance, mirroring the way databases and software systems operate in practice.
Expressive Power and Inductive Definitions
To make the framework practical for real-world applications, the authors utilize FO(ID)—First-Order logic extended with Inductive Definitions. While pure first-order logic is powerful, it struggles to represent recursive properties, such as the transitive closure of a graph (e.g., "is vertex A reachable from vertex B?").
By incorporating inductive definitions, the framework allows modelers to express recursive properties using a syntax similar to logic programming. Crucially, FO(ID) retains classical semantics, avoiding the conceptual overhead of the non-classical logic used in ASP. This "secret sauce" allows for high-level modeling without sacrificing the clarity of classical logic.
Theoretical Results
The paper establishes several key theorems that define the boundaries and capabilities of the MX framework:
- Complexity of General MX: The authors prove that the general First-Order Model Extension problem is NEXPTIME-complete.
- Capturing NP: When the formula $\phi$ is fixed (the parameterized version), the Model Extension task captures exactly the complexity class NP. This result is significant because it demonstrates that the framework is "just right"—it is powerful enough to solve any NP problem without introducing unnecessary computational complexity.
- FO(ID) Efficiency: The authors show that extending the logic with Inductive Definitions does not increase the computational cost; FO(ID) still captures exactly NP.
- Unified Theory: The paper provides formal reductions showing how SAT, CSP, and ASP can be viewed as specific, restricted cases of the Model Extension framework, positioning MX as a unifying theory for declarative problem solving.
Practical Considerations and Future Work
While the theoretical foundation is robust, the authors identify several areas for practical development. The success of the MX framework depends on the creation of "smart grounding" engines—tools that can translate high-level FO(ID) logic into efficient, propositional formulas suitable for SAT-style solvers.
Furthermore, for industrial utility, the framework requires enhanced support for arithmetic and aggregates (such as "sum" or "count"). The authors emphasize that these features must be integrated carefully to ensure they do not inadvertently push the complexity beyond NP. Future research will focus on overcoming grounding bottlenecks, which currently represent the primary performance hurdle in translating logical descriptions into solvable constraints.
Conclusion
The Model Extension framework offers a compelling new path for NP search problems. By staying within the realm of classical logic and adding inductive definitions, the authors provide a system that is both mathematically "clean" and practically expressive. This work lays the groundwork for a new generation of solvers that combine the best aspects of SAT, CSP, and ASP into a single, unified logical framework.
Summary updated