cs.LONov 6, 2026

Optimal Probabilistic Answer Set Programming: Complexity and Implementations

Authors: Damiano Azzolini, Giuseppe Mazzotta, Francesco Ricca, Fabrizio Riguzzi

Organizations: University of Ferrara · University of Calabria

Abstract

Probabilistic Answer Set Programming (PASP) extends Answer Set Programming with the possibility of representing uncertain data. Among the possible available semantics, we focus here on the credal semantics. In this setting, prior work has focused exclusively on plain ASP programs, i.e., programs without optimization constructs. However, many real world tasks define optimality criteria over the possible solutions, which cannot be conveniently modeled with existing probabilistic ASP frameworks. In this paper, we close this gap and propose optimal Probabilistic Answer Set Programming, which extends PASP by also allowing weak constraints, which are the standard optimization construct of ASP. We define the semantics of such programs, study the computational complexity of the inference and most probable explanation tasks, and propose practical implementations based on Algebraic Model Counting and Answer Set Programming with Quantifiers. An empirical evaluation of the proposed approach on three real world tasks confirms the applicability of our framework.

Explore similar work

CardsList
  1. 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation

    May 26, 2026Andrea Cuteri, Giuseppe Mazzotta, Francesco RiccaLogic ProgrammingCounterexample-Guided Refinement

  2. Answer Set Programming Energised! End-to-End Neurosymbolic Reasoning and Learning with ASP and Energy Based Models

    Jul 9, 2026Jakob Suchan, Julius Monsen, Salim Baloch +1Energy-Based ModelsAnswer Set Programming

  3. Using ASP(Q) to Handle Inconsistent Prioritized Data

    Apr 23, 2026Meghyn Bienvenu, Camille Bourgaux, Robin Jean +1Answer Set Programming