A Novel Framework for Reasoning over Optimization Problems in Probabilistic Answer Set Programming

Probabilistic logic-based languages offer an expressive framework for encoding uncertain information in a human-interpretable way. Among existing formalisms, Probabilistic Answer Set Programming (PASP) stands out for its ease of modeling complex scenarios. The current definition of PASP is limited to programs consisting of disjunctive rules and probabilistic facts only. To enhance the expressivity of the framework, we introduce Optimal Probabilistic Answer Set Programming, which extends the language by allowing the inclusion of weak constraints within PASP specifications. We motivate this extension through some real-world application scenarios and present a detailed computational complexity analysis for both the inference and Most Probable Explanation (MPE) tasks.