Declarative Programming of Search Problems with Built-in Arithmetic

Eugenia Ternovska, David G. MitchellIJCAI 2009

Abstract

Declarative modeling languages allow users to specify combinatorial search problems by describing what a solution looks like rather than how to find it. However, integrating arithmetic and infinite domains (such as the natural numbers) into these frameworks often leads to undecidability or excessive computational complexity. This paper introduces a formal framework for Embedded Model Expansion (MX) that incorporates built-in arithmetic while ensuring the language remains within the complexity class NP. By utilizing a "double-guarded" logic fragment, the authors provide a theoretical guarantee that expressive modeling languages can be both powerful and efficiently solvable.

Introduction

In the realm of combinatorial optimization and search, declarative languages—such as those used in constraint programming or answer set programming—rely on the concept of Model Expansion (MX). In this paradigm, a user provides a logical formula and an input structure; the solver's task is to expand that structure to satisfy the formula.

While effective for purely relational problems, real-world applications (e.g., scheduling, logistics, and finance) necessitate arithmetic operations, aggregates like SUM or MAX, and reasoning over potentially infinite domains. Standard First-Order logic (FO) becomes problematic when infinite domains like the natural numbers are introduced, as it can easily express problems that are undecidable. The challenge addressed in this research is to design a logic that allows for natural arithmetic modeling while strictly controlling expressive power to ensure every representable problem is guaranteed to be in NP.

The Double-Guarded Fragment ($GGF_k$)

To bridge the gap between expressiveness and complexity, the authors propose Embedded MX with Arithmetic. In this approach, finite problem instances are embedded into an infinite "secondary" structure—specifically, the natural numbers equipped with standard arithmetic operations.

The core innovation is the Double-Guarded Fragment ($GGF_k$). Bounding quantification is a known technique in logic, but the authors demonstrate that when arithmetic is involved, a more rigorous approach is required. They introduce two distinct types of guards:

  1. Lower Guards: These restrict the range of quantified variables to the "active domain" (elements that exist within the specific problem instance).
  2. Upper Guards: These restrict the range of "expansion predicates" (the new relations the solver is attempting to find). This prevents the search space from exploding into the infinite background domain, ensuring that the set of solutions remains finite and manageable.

Aggregates and Inductive Definitions

Practical modeling requires more than just basic predicates; it requires the ability to perform calculations over sets of data. The paper formally integrates Multiset Operations into the logic. By treating aggregates (sum, product, min, max) as functions over multisets, the authors provide a rigorous semantics for SQL-style queries within a search framework. These operations are defined such that they remain polynomial-time computable, preserving the overall complexity bounds of the system.

Furthermore, the authors recognize that some problems require numbers not explicitly present in the input—for example, finding the factors of a large integer or calculating intermediate costs. To handle this, they extend the logic with Inductive Definitions (FO(ID)). This allows users to define new guard relations inductively, provided these definitions are "good" (computable in polynomial time), further increasing the language's flexibility without sacrificing efficiency.

Theoretical Results: Capturing NP

The primary contribution of the paper is a "Capturing Result" in descriptive complexity. The authors prove Theorem 1: The double-guarded logic $GGF_k$ captures the complexity class NP on small-cost arithmetical structures.

In this context, "capturing NP" means the logic can express exactly the set of problems that a non-deterministic Turing machine can solve in polynomial time. The "small-cost" restriction ensures that the binary encoding of the largest number in the structure is polynomial relative to the size of the domain. This result is significant because it provides a mathematical "gold standard," proving that the language is as powerful as possible while still being solvable by NP-level solvers (like SAT or SMT solvers).

Conclusion and Future Work

This research bridges the gap between abstract mathematical logic and the practical requirements of constraint modeling languages like ESSENCE or Zinc. By formalizing the use of aggregates and double-guarded quantification, the authors provide a theoretical foundation for the next generation of declarative solvers.

While the "small-cost" assumption covers the vast majority of practical search problems, future work may explore even weaker restrictions. Additionally, while the current work focuses on the underlying logic and complexity, the authors suggest that the guarded fragments are specifically designed to be "grounded" (automatically reduced) to SAT, paving the way for new, more efficient implementation strategies in declarative programming.

Summary updated

BibTeX
@inproceedings{ternovska2009declarative,
  author = {Eugenia Ternovska and David G. Mitchell},
  title = {{Declarative Programming of Search Problems with Built-in Arithmetic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure