Quantifying over Optimum Answer Sets
Answer Set Programming with Quantifiers (ASP(Q)) has been introduced to provide a natural extension of ASP modeling to problems in the polynomial hierarchy (PH). However, ASP(Q) lacks a method for encoding in an elegant and compact way problems requiring a polynomial number of calls to an oracle in $\Sigma_n^p$ (that is, problems in $\Delta_{n+1}^p$). Such problems include, in particular, optimization problems. In this paper we propose an extension of ASP(Q), in which component programs may contain weak constraints. Weak constraints can be used both for expressing local optimization within quantified component programs and for modeling global optimization criteria. We showcase the modeling capabilities of the new formalism through various application scenarios. Further, we study its computational properties obtaining complexity results and unveiling non-obvious characteristics of ASP(Q) programs with weak constraints.
Code (0)
등록된 구현이 없습니다.
Tasks
global-optimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Quantifying and Understanding Uncertainty in Large Reasoning Models
Large Reasoning Models (LRMs) have recently demonstrated significant improvements in complex reasoning. While quantifying generation uncertainty in LRMs is crucial, traditional methods are often insufficient because they…
Answer GenerationMultiple Meta-model Quantifying for Medical Visual Question Answering
Transfer learning is an important step to extract meaningful features and overcome the data limitation in the medical Visual Question Answering (VQA) task. However, most of the existing medical VQA methods rely on extern…
Medical Visual Question AnsweringMeta-LearningQuestion AnsweringTransfer Learning+2Conformal Feedback Alignment: Quantifying Answer-Level Reliability for Robust LLM Alignment
Preference-based alignment like Reinforcement Learning from Human Feedback (RLHF) learns from pairwise preferences, yet the labels are often noisy and inconsistent. Existing uncertainty-aware approaches weight preference…
Reinforcement LearningIASCAR: Incremental Answer Set Counting by Anytime Refinement
Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have many answer sets that cannot be enumerated in practice, but counting still allows quantifying…
Beyond statistical significance: Quantifying uncertainty and statistical variability in multilingual and multitask NLP evaluation
We introduce a set of resampling-based methods for quantifying uncertainty and statistical precision of evaluation metrics in multilingual and/or multitask NLP benchmarks. We show how experimental variation in performanc…
Machine TranslationQuestion Answering