Complexity Results in Optimistic/Pessimistic Preference Reasoning - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2016

Complexity Results in Optimistic/Pessimistic Preference Reasoning

Abstract

Preference reasoning is a central problem in decision support. There exist various ways to interpret a set of qualitative preferences. Conditional preference logics allow to deal with semantics such as optimistic, pessimistic, strong or not. In this paper, we study the complexity of the main problems in optimistic/pessimistic preference logic: undominated, consistency and dominance. We show that they are all NP-hard in general, with some becoming polynomial under specific semantics. Our second contribution is to show that the dominance problem, which has an online component in its definition, is compilable to polynomial time.

Domains

Logic [math.LO]
Fichier principal
Vignette du fichier
ictai16.pdf (264.95 Ko) Télécharger le fichier
SlidesIctai.pdf (2.61 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01987872 , version 1 (21-01-2019)

Identifiers

Cite

Christian Bessiere, Remi Coletta, Gaelle Hisler, Anastasia Paparrizou. Complexity Results in Optimistic/Pessimistic Preference Reasoning. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2016, San Jose, CA, United States. pp.930-937, ⟨10.1109/ICTAI.2016.0144⟩. ⟨lirmm-01987872⟩
136 View
154 Download

Altmetric

Share

More