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

• URL: http://arxiv.org/abs/2605.27338v1
• Date: Tue, 26 May 2026 17:44:39 GMT
• Title: 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
• Abstract summary: This paper focuses on the class of ASP(Q) programs with two quantifiers and weak constraints, denoted as 2-ASP(Q)w.<n>On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)w programs.<n>On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system.
• Score: 4.760079434948197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: ASP(Q) extends Answer Set Programming (ASP) with Quantifiers over answer sets. In this paper we focus on the class of ASP(Q) programs with two quantifiers and weak constraints, denoted as 2-ASP(Q)^w. 2-ASP(Q)^w is a practically relevant fragment of ASP(Q) that is expressive enough to capture optimization problems up to the class Delta_3^P. On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)^w programs, including tight completeness results and the analysis of nontrivial cases that have not been addressed in previous works. On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system, that rely on a Counterexample-Guided Abstraction Refinement (CEGAR) technique tailored to ASP(Q). An experimental evaluation on hard benchmarks from different application domains shows that the proposed techniques are effective in practice.

Related papers

• ClarifyCodeBench: Evaluating LLMs on Clarifying Ambiguous Requirements for Code Generation [54.788849448970154]
  We introduce ClarifyCodeBench, a novel interactive benchmark for evaluating Large Language Models' capability in resolving requirement ambiguity.<n>We conduct a systematic evaluation of six state-of-the-art LLMs using ClarifyCodeBench.<n>Our empirical results yield three critical insights: 1) Capability Decoupling: Strong code generation performance does not inherently translate to effective requirement clarification; 2) The Reasoning Paradox: While increased computational thinking enhances code correctness, it yields marginal gains in identifying ambiguities.
  arXiv  Detail & Related papers  (2026-07-01T09:58:59Z)
• Counting Answer Sets of Disjunctive Answer Set Programs [28.739355096774155]
  We present SharpASP-SR, a novel framework for counting answer sets of disjunctive logic programs.<n>We show that SharpASP-SR significantly outperforms existing counters on instances with large answer set counts.
  arXiv  Detail & Related papers  (2025-07-15T18:41:19Z)
• SPARE: Single-Pass Annotation with Reference-Guided Evaluation for Automatic Process Supervision and Reward Modelling [58.05959902776133]
  We introduce Single-Pass.<n>with Reference-Guided Evaluation (SPARE), a novel structured framework that enables efficient per-step annotation.<n>We demonstrate SPARE's effectiveness across four diverse datasets spanning mathematical reasoning (GSM8K, MATH), multi-hop question answering (MuSiQue-Ans), and spatial reasoning (SpaRP)<n>On ProcessBench, SPARE demonstrates data-efficient out-of-distribution generalization, using only $sim$16% of training samples compared to human-labeled and other synthetically trained baselines.
  arXiv  Detail & Related papers  (2025-06-18T14:37:59Z)
• T$^2$: An Adaptive Test-Time Scaling Strategy for Contextual Question Answering [49.5489716597489]
  We present T$2$: Think-to-Think, a novel framework that dynamically adapts reasoning depth based on question complexity.<n>T$2$ works through four key steps: decomposing questions into structural elements, generating similar examples with candidate reasoning strategies, evaluating these strategies against multiple criteria, and applying the most appropriate strategy to the original question.
  arXiv  Detail & Related papers  (2025-05-23T03:18:02Z)
• Recursive Decomposition with Dependencies for Generic Divide-and-Conquer Reasoning [48.829971427616854]
  We introduce Recursive Decomposition with Dependencies (RDD), a scalable divide-and-conquer method for solving reasoning problems.<n>RDD can be directly applied to a new problem class even in the absence of any task-specific guidance.<n>We evaluate our approach on two benchmarks with six difficulty levels each and in two in-context settings.
  arXiv  Detail & Related papers  (2025-05-05T11:24:20Z)
• Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [49.362750475706235]
  Reinforcement Learning (RL) plays a crucial role in aligning large language models with human preferences and improving their ability to perform complex tasks.<n>We introduce Direct Q-function Optimization (DQO), which formulates the response generation process as a Markov Decision Process (MDP) and utilizes the soft actor-critic (SAC) framework to optimize a Q-function directly parameterized by the language model.<n> Experimental results on two math problem-solving datasets, GSM8K and MATH, demonstrate that DQO outperforms previous methods, establishing it as a promising offline reinforcement learning approach for aligning language models.
  arXiv  Detail & Related papers  (2024-10-11T23:29:20Z)
• Quantifying over Optimum Answer Sets [6.390468088226495]
  ASP(Q) lacks a method for encoding modeling in an elegant and compact way. We propose an extension of ASP(Q) in which component programs may contain weak constraints. We showcase the modeling capabilities of the new formalism through various application scenarios.
  arXiv  Detail & Related papers  (2024-08-14T17:53:13Z)
• An efficient solver for ASP(Q) [4.198045959496482]
  ASP(Q) extends Answer Set Programming (ASP) to allow for declarative and modular modeling of problems from the hierarchy. We present a new implementation that builds on the ideas of qasp and features both a more efficient encoding procedure and new optimized encodings of ASP(Q) programs in QBF.
  arXiv  Detail & Related papers  (2023-05-17T07:59:53Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization [33.12181620473604]
  We study a Fitted Q-Iteration with two-layer ReLU neural network parametrization, and find the sample complexity guarantees for the algorithm. We show that this approach achieves a sample complexity of $tildemathcalO (1/epsilon2)$, which is order-optimal.
  arXiv  Detail & Related papers  (2022-11-14T19:00:24Z)
• Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
  We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems. First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints. We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect.
  arXiv  Detail & Related papers  (2022-05-16T08:10:40Z)
• Harnessing Incremental Answer Set Solving for Reasoning in Assumption-Based Argumentation [1.5469452301122177]
  Assumption-based argumentation (ABA) is a central structured argumentation formalism. Recent advances in answer set programming (ASP) enable efficiently solving NP-hard reasoning tasks of ABA in practice.
  arXiv  Detail & Related papers  (2021-08-09T17:34:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.