# Complexity of Abduction in Łukasiewicz Logic

Katsumi Inoue, Daniil Kozhemiachenko

► To cite this version:

Katsumi Inoue, Daniil Kozhemiachenko. Complexity of Abduction in Łukasiewicz Logic. 2025. hal-05348680

HAL Id: hal-05348680

https://hal.science/hal-05348680v1

Preprint submitted on 5 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complexity of Abduction in Łukasiewicz Logic

Katsumi Inoue¹, Daniil Kozhemiachenko²

¹National Institute of Informatics, Tokyo, Japan

²Aix Marseille Univ, CNRS, LIS, Marseille, France
inoue@nii.ac.jp, daniil.kozhemiachenko@lis-lab.fr

## Abstract

We explore the problem of explaining observations in contexts involving statements with truth degrees such as ‘the lift is loaded’, ‘the symptoms are severe’, etc. To formalise these contexts, we consider infinitely-valued Łukasiewicz fuzzy logic Ł. We define and motivate the notions of abduction problems and explanations in the language of Ł expanded with ‘interval literals’ of the form $p \ge c$, $p \le c$, and their negations that express the set of values a variable can have. We analyse the complexity of standard abductive reasoning tasks (solution recognition, solution existence, and relevance / necessity of hypotheses) in Ł for the case of the full language and for the case of theories containing only disjunctive clauses and show that in contrast to classical propositional logic, the abduction in the clausal fragment has lower complexity than in the general case.

## 1 Introduction

Abduction, deduction, and induction are three main forms of reasoning (Flach and Kakas 2000). Abduction (finding explanations) has multiple applications in artificial intelligence, such as diagnosis (El Ayeb, Marquis, and Rusinowitch 1993; Josephson and Josephson 2009; Koitz-Hristov and Wotawa 2018), commonsense reasoning (Paul 1993; Bhagavatula et al. 2020), formalisation of scientific reasoning (Magnani 2011), and machine learning (Dai et al. 2019). In *logic-based abduction* (Eiter and Gottlob 1995), the reasoning task is to find an explanation for an observation $\chi$ from a theory $\Gamma$, i.e., a formula $\phi$ s.t. $\Gamma, \phi \models \chi$ but $\Gamma, \phi \not\models \bot$ (i.e., $\Gamma$ and $\phi$ should *consistently entail* $\chi$).

Observe, however, that in many applications, one needs not only to state whether a formula is true but also to specify *to which degree* it holds. E.g., a lift may be safe to use only when loaded to at least 5% of its maximal capacity (otherwise, its software will register it as empty) and to no more than 90% of the capacity. Or the cruising speed of a car can be defined as 60...90 kmh (with the maximal speed being 150 kmh). As classical logic has only two values, it is not well-suited to reason about contexts involving truth degrees. On the other hand, *fuzzy logics* evaluate formulas in the real-valued interval [0, 1] and thus are much better suitable to formalising such contexts than classical logic. In particular, to formalise the examples above, we can set $v(l) \ge 0.05$ and $v(s) \in [0.4, 0.6]$ where the truth degrees of $l$ and $s$ denote,

respectively, the load of the lift and the speed of the car w.r.t. its maximal speed.

**Fuzzy Logic** Originally (Zadeh 1965; Zadeh 1975) fuzzy logics were introduced to reason about imprecise statements such as ‘it is cold outside’, ‘the symptoms are severe’, etc. The values between [0, 1] are interpreted as degrees of truth from 0 (absolutely false) to 1 (absolutely true). Fuzzy logic has also been applied to reasoning about uncertainty (cf., e.g., (Hájek and Tulipani 2001) and (Baldi, Cintula, and Noguera 2020)) and beliefs (Rodriguez et al. 2022). In knowledge representation and reasoning, fuzzy logics have found multiple applications in representing graded and fuzzy ontologies (Straccia 2016). In such ontologies, concept assertions and terminological axioms have degrees of truth. Moreover, fuzzy versions of description logics and their computational properties have been extensively investigated (Borgwardt and Peñaloza 2012; Borgwardt 2014; Borgwardt, Distel, and Peñaloza 2014; Borgwardt and Peñaloza 2017).

In addition to that, fuzzy logic has found multiple applications in artificial intelligence. Recent work on machine learning tries to combine perception by deep learning and symbolic knowledge representation. Neurosymbolic frameworks such as (Diligenti, Gori, and Saccà 2017; Badreddine et al. 2022) adopt semantics of fuzzy logic to support learning and reasoning in real-world domains. (Krieken, Acar, and Harmelen 2022) analyse how different fuzzy logic semantics affect the behaviour of learning. Fuzzy logic has also been used in reasoning problems with knowledge graphs (Chen, Hu, and Sun 2022) and MaxSAT (Haniková, Manyà, and Vidal 2023). Furthermore, t-norms (functions used to interpret conjunctions in fuzzy logic) are applied for autonomous driving with requirements (Stoian, Giunchiglia, and Lukasiewicz 2023).

**Abduction in Fuzzy Logic** Abduction in different systems of fuzzy logic has long attracted attention. To the best of our knowledge, it was first presented by (Yamada and Mukaidono 1995). There, the authors formalised abduction problems in the infinitely-valued Łukasiewicz fuzzy logic Ł and proposed explanations in the form of *fuzzy sets*, i.e., assignments of values from [0, 1] to propositional
variables. This approach was further expanded by (Vojtáš 1999) to Gödel and Product fuzzy logics. Solutions to abduction problems in multiple fuzzy logics were further systematised by (d’Allonnes, Akdag, and Bouchon-Meunier 2007) and (Chakraborty et al. 2013). Abduction in fuzzy logic has found multiple applications, in particular, diagnosis (Miyata, Furuhashi, and Uchikawa 1998), machine learning (Bergadano, Cutello, and Gunetti 2000), fuzzy logic programming (Vojtáš 2001; Ebrahim 2001), decision-making and learning in the presence of incomplete information (Mellouli and Bouchon-Meunier 2003; Tsypyschev 2017), and robot perception (Shanahan 2005).

**Contributions** Still, the complexity of fuzzy abduction largely remains unexplored. To the best of our knowledge, the only discussion is given by (Vojtáš 1999). There, the author explores fuzzy abduction in definite logic programmes (i.e., sets of rules of the form $\langle B \leftarrow A_1, \dots, A_n, x \rangle$ where each $A_i$ is an atom and $x$ belongs to the real-valued interval $[0, 1]$). In particular, the author claims (cf. (Vojtáš 1999, §4.4) for details) that '[a]s linear programming is lying in NP complexity class (even much lower) as prolog does, to find minimal solutions for a definite [fuzzy logic programming abduction problem] ... does not increase the complexity and remains in NP'. Thus, there seems to be no formal study of the complexity of abduction in fuzzy logic.

In this paper, we make a step towards a study of the complexity of abduction in fuzzy logic. We concentrate on the Łukasiewicz logic as it is one of the most expressive ones. In particular, it can express rational numbers and continuous linear functions over $[0, 1]$ (cf. (McNaughton 1951) for details). In addition, it still retains many classical relations between its conjunction, disjunction, implication, and negation. We formalise abduction in Ł and explore its computational properties. Our contribution is twofold. First, we propose and motivate a new form of solutions — interval terms — that allow to express intervals of values a variable is permitted to have. Second, we establish an (almost) complete characterisation of the complexity of standard reasoning problems (solution recognition, solution existence, relevance and necessity of hypotheses) for the case of theories containing arbitrary formulas and those comprised of disjunctive clauses.

**Plan of the Paper** The paper is structured as follows. In Section 2, we present the Łukasiewicz logic. In Section 3, we propose and motivate interval terms that we will use as solutions to Łukasiewicz abduction problems. Sections 4 and 5 are dedicated to the study of the complexity of abductive reasoning in the Łukasiewicz logic and its clausal fragment. Finally, we summarise our results and provide a plan for future work in Section 6. Due to limited space, some proofs are put into the appendix of the full version (Inoue and Kozhemiachenko 2025).

## 2 Łukasiewicz Logic

We begin with the language of Łukasiewicz logic (Ł). We fix a countable set $\text{Pr}$ of propositional variables and define

$\mathcal{L}_Ł$ via the following grammar.

$$ \mathcal{L}_Ł \ni \phi := p \in \text{Pr} \mid \neg\phi \mid (\phi \odot \phi) \mid (\phi \oplus \phi) \mid (\phi \to \phi) $$

**Convention 1 (Notation).** We use the following shorthands:

$$ \top := p \oplus \neg p \quad \bot := p \odot \neg p \quad \phi \leftrightarrow \chi := (\phi \to \chi) \odot (\chi \to \phi) $$

For a set of formulas $\Gamma$ and a formula $\phi$, we write $\text{Pr}(\phi)$ and $\text{Pr}[\Gamma]$ to denote the set of all variables occurring in $\phi$ and $\Gamma$, respectively.

We use $\mathbb{R}$ and $\mathbb{Q}$ to denote the sets of real and rational numbers, respectively. When dealing with intervals, square brackets mean that the endpoint is included in the interval, and round brackets that it is excluded. Lower index $\mathbb{Q}$ means that the interval contains rational numbers only. E.g.,

$$ \begin{aligned} [1/2, 2/3] &= \{x \mid x \in \mathbb{R}, x \ge 1/2, x \le 2/3\} \\ (1/2, 2/3]_{\mathbb{Q}} &= \{x \mid x \in \mathbb{Q}, x > 1/2, x \le 2/3\} \end{aligned} $$

The semantics of Ł is given in the next definition.

**Definition 1 (Semantics of Łukasiewicz logic).** An Ł-valuation is a function $v: \text{Pr} \to [0, 1]$ extended to the complex formulas as follows:

$$ \begin{aligned} v(\neg\phi) &= 1 - v(\phi) \\ v(\phi \odot \chi) &= \max(0, v(\phi) + v(\chi) - 1) \\ v(\phi \oplus \chi) &= \min(1, v(\phi) + v(\chi)) \\ v(\phi \to \chi) &= \min(1, 1 - v(\phi) + v(\chi)) \end{aligned} $$

We say that $\phi \in \mathcal{L}_Ł$ is Ł-valid ($Ł \models \phi$) if $v(\phi) = 1$ for every Ł-valuation $v$; $\phi$ is Ł-satisfiable if $v(\phi) = 1$ for some Ł-valuation $v$.

We define two notions of equivalence — strong equivalence ($\phi \cong_Ł \chi$) and weak equivalence ($\phi \simeq_Ł \chi$):

$$ \begin{aligned} \phi \cong_Ł \chi &\text{ iff } \forall v : v(\phi) = v(\chi) \\ \phi \simeq_Ł \chi &\text{ iff } \forall v : v(\phi) = 1 \Leftrightarrow v(\chi) = 1 \end{aligned} $$

Given a finite $\Gamma \subset \mathcal{L}_Ł$, $\Gamma$ entails $\chi$ in Ł ($\Gamma \models_Ł \chi$) iff $v(\chi) = 1$ in every $v$ s.t. $v(\phi) = 1$ for all $\phi \in \Gamma$, and that $\Gamma$ consistently entails $\chi$ in Ł ($\Gamma \models_{Ł}^{\text{cons}} \chi$) iff $\Gamma \nvDash_Ł \top$ and $\Gamma \nvDash_Ł \chi$.

We note some important semantical properties of Ł. First, every connective behaves classically on $\{0, 1\}$: in particular, $\oplus$ behaves like disjunction and $\odot$ like conjunction. Thus, we will call $\oplus$ strong disjunction and $\odot$ strong conjunction.

Second, deduction theorem does not hold for $\models_Ł$: indeed, while $p \models_Ł p \odot p$, it is easy to show that $Ł \nvDash p \to (p \odot p)$ by setting $v(p) = 1/2$. Third, $\odot$ and $\oplus$ are not idempotent: setting $v(p) = 1/2$, we have that $v(p \odot p) = 0$ and $v(p \oplus p) = 1$.

Still, $\neg$, $\odot$, $\oplus$, and $\to$ interact in an expected manner. In particular, it is easy to check that $v(\top) = 1$ and $v(\bot) = 0$ for every valuation and that the following pairs of formulas are indeed strongly equivalent:

$$ \begin{aligned} \neg(\phi \odot \chi) &\equiv_Ł \neg\phi \oplus \neg\chi &\neg(\phi \oplus \chi) &\equiv_Ł \neg\phi \odot \neg\chi \\ \neg(\phi \to \chi) &\equiv_Ł \phi \odot \neg\chi &\neg\phi \oplus \chi &\equiv_Ł \phi \to \chi \quad (1) \\ \neg\neg\phi &\equiv_Ł \phi &\phi \odot \phi &\equiv_Ł \psi \end{aligned} $$
It is also important to observe that weak conjunction (`∧`) and disjunction (`∨`) are definable as follows:

$$ \phi \lor \chi := (\phi \rightarrow \chi) \rightarrow \chi \quad \phi \land \chi := \neg(\neg \phi \lor \neg \chi) \quad (2) $$

Using Definition 1, one can recover semantics of `∧` and `∨`:

$$ v(\phi \land \chi) = \min(v(\phi), v(\chi)) \qquad v(\phi \lor \chi) = \max(v(\phi), v(\chi)) $$

In what follows, we will write `$\Gamma, \phi \models_K \chi$` as a shorthand for `$\Gamma \cup \{\phi\} \models_K \chi$`. Similarly, if the set of premises is given explicitly, we omit brackets. E.g., `$\phi, \chi \models_K \psi$` stands for `$\{\phi, \chi\} \models_K \psi$`. Note, furthermore, that the comma in the set of premises can be equivalently interpreted as `∧` and `⊙` as `$\{\phi \land \chi\} \simeq_K (\phi \odot \chi)$`. Hence, for `$\Gamma = \{\phi_1, \dots, \phi_n\}$`, we have

$$ \Gamma \models_K \chi \text{ iff } \bigcirc_{i=1}^{n} \phi_i \models_K \chi \text{ iff } \bigwedge_{i=1}^{n} \phi_i \models_K \chi $$

We finish the section by recalling the complexity of `K`. It is known (Mundici 1987, Theorem 3.4) that satisfiability of arbitrary formulas in `K` is NP-complete while validity and entailment are coNP-complete (Haniková 2011, Corollary 4.1.3) just as in classical propositional logic (CPL).

**Proposition 1.**

1. `K`-satisfiability is NP-complete.

2. Entailment in `K` is coNP-complete.

## 3 Interval Terms

Before proceeding to the formal presentation of abduction, let us introduce the terms that we will be using in solutions. Traditionally, the form of solutions is restricted to conjunctions of literals (terms). In this case, a solution corresponds to a statement of facts. Moreover, in this case, the logically weakest solutions are the subset-minimal ones. We begin with Łukasiewicz counterparts of classical terms and clauses.

**Definition 2 (Simple literals, clauses, and terms).**

* A simple literal is a propositional variable or its negation.

* A simple clause is a strong disjunction of simple literals, i.e., a formula of the form $\bigoplus_{i=1}^n l_i$ for some $n \in \mathbb{N}$.

* A simple term is a strong conjunction of simple literals, i.e., a formula of the form $\bigcirc_{i=1}^n l_i$ for some $n \in \mathbb{N}$.

One can observe, however, that simple terms from Definition 2 are too restrictive if we want to use them as solutions for abduction problems. Indeed, a simple term $\tau$ has value 1 iff all its literals have value 1. But in a context with fuzzy propositions, we might need to express statements such as 'p has value $\frac{2}{3}$' or 'q has value at least $\frac{1}{4}$'. The following example illustrates this situation.

**Example 1.** Assume that we have a lift with a weight sensor that controls two indicators: green and blue. The green indicator is on when the weight sensor detects the load of at least $\frac{1}{4}$ of its maximal capacity. Blue light is on when the lift is loaded to at most $\frac{2}{3}$ of its maximal capacity. We see that both indicators are lit.

Let us now formalise this problem in `K`. We interpret the value of `c` as the percentage of capacity to which the lift is loaded and translate the condition 'the lift is loaded to at

least $1/4$ of its capacity' as $c \oplus c \oplus c \oplus c$. Observe that $v(c \oplus c \oplus c \oplus c) = 1$ iff $v(c) \ge 1/4$. To represent the other condition 'the lift is loaded to at most $2/3$ of its capacity', we write $\neg c \oplus \neg c \oplus \neg c$. We have that $v(\neg c \oplus \neg c \oplus \neg c) = 1$ iff $v(\neg c) \ge 1/3$, i.e., iff $v(c) \le 2/3$. Finally, we use `g` and `b` to represent that the green and blue lights are on. We obtain the following theory $\Gamma_{\text{lift}}$ and observation $\chi_{\text{lift}}$:

$$ \Gamma_{\text{lift}} = \{(c \oplus c \oplus c \oplus c) \leftrightarrow g, (\neg c \oplus \neg c \oplus \neg c) \leftrightarrow b\} $$

$$ \chi_{\text{lift}} = g \odot b $$

To explain why both indicators are on, we need to present a formula $\phi$ s.t. $\Gamma_{\text{lift}}, \phi \models_K^{\text{cons}} g \odot b$. For this, we need that $v(\neg c \oplus \neg c \oplus \neg c) = 1$ and $v(c \oplus c \oplus c \oplus c) = 1$ in every valuation that makes $\Gamma_{\text{lift}}$ true. As we noted above, this requires that $v(c) \in [\frac{1}{4}, \frac{2}{3}]$. On the other hand, a simple term $\tau$ has value 1 iff all its literals have value 1 (i.e., all variables in $\tau$ should have value 0 or 1). Thus, there is no simple term $\tau$ containing `c` or $\neg c$ s.t. $\Gamma_{\text{lift}}, \tau \models_K^{\text{cons}} \chi$. Hence $\phi$ cannot be a simple term.

One way to circumvent this problem is to adopt the proposal of (Yamada and Mukaidono 1995) and (Vojtáš 1999) and define solutions to fuzzy abduction problems as sets of assignments of values to propositional variables. This approach, however, has a drawback. In this setting, one can only express exact values of variables but not intervals of their values. Now, observe from Example 1 that any assignment of a value from $[\frac{1}{4}, \frac{2}{3}]$ to `c` solves $\langle \Gamma_{\text{lift}}, \chi_{\text{lift}} \rangle$. Thus, in the general case, it is impossible to generate the set of all solutions as there are infinitely many of them. Moreover, it may be problematic to choose between different values.

In this section, we propose an alternative. For that, we define terms that allow us to express both exact values of variables and their intervals and compare different solutions w.r.t. entailment in `K`. Moreover, as we will see in Section 4, every abduction problem will have only finitely many solutions in our setting.

**Definition 3 (Rational interval literals, terms, and clauses).**
Let $p \in \text{Pr}, \diamond \in \{\le, \ge, <, >\}$, and $c \in [0, 1]_{\diamond}$.

* A rational interval literal has the form $p \diamond c$ or $\neg(p \diamond c)$. The semantics of rational interval literals is as follows:

$$ v(p \diamond c) = \begin{cases} 1 & \text{if } v(p) \diamond c \\ 0 & \text{otherwise} \end{cases} \qquad v(\neg(p \diamond c)) = 1 - v(p \diamond c) $$

For a rational interval literal $p \diamond c$, we call `c` its boundary value and call the set $\{v(p) | v(p \diamond c) = 1\}$ its permitted values.

* A rational interval term has the form $\bigcirc_{i=1}^n \lambda_i$ with each $\lambda_i$ being an interval literal.

* A rational interval clause has the form $\bigoplus_{i=1}^n \lambda_i$ with each $\lambda_i$ being an interval literal.

**Convention 2.** We use $\mathcal{L}_K^{\mathcal{Q}}$ to denote the language obtained from $\mathcal{L}_K$ by expanding it with rational interval literals. We will mostly write 'interval literals (terms, clauses)' instead of 'rational interval literals (terms, clauses)'. The notions of `K`-validity, satisfiability and entailment are preserved from Definition 1. We will also utilise notation from Convention 1 for $\mathcal{L}_K^{\mathcal{Q}}$. Additionally, given an interval literal $p \diamond c$, we use
p♦c to denote ¬(p♦c). Finally, given a literal λ and a term or clause ϑ, we write λ ∈ ϑ to designate that λ occurs in ϑ.

We observe that it follows from (1) that interval clauses and terms are dual in the following sense:

$$ \neg \bigcirc_{i=1}^{n} (p_i \diamond \mathbf{c}_i) \equiv_{\mathcal{L}} \bigoplus_{i=1}^{n} (p_i \diamond \mathbf{c}_i) \quad \neg \bigoplus_{i=1}^{n} (p_i \diamond \mathbf{c}_i) \equiv_{\mathcal{L}} \bigcirc_{i=1}^{n} (p_i \diamond \mathbf{c}_i) \quad (3) $$

*Remark 1.* From Definition 3, it is clear that interval terms generalise simple terms in the following sense: for every simple term τ, there is an interval term τ♦ s.t. τ ≃< τ ♦. Indeed, given $\tau = \bigcirc_{i=1}^{m} p_i \odot \bigcirc_{j=1}^{n} \neg q_j$, we can define $\tau^{\diamond} = \bigcirc_{i=1}^{m} (p_i \ge \mathbf{1}) \odot \bigcirc_{j=1}^{n} (q_j \le \mathbf{0})$. Moreover,

$$ p \le \mathbf{c} \models_{\mathcal{L}} p \le \mathbf{c}' \text{ iff } p \le \mathbf{c} \models_{\mathcal{L}} p \ge \mathbf{c}' \text{ iff } p \ge \mathbf{c}' \models_{\mathcal{L}} p \ge \mathbf{c}' $$

and similarly for the literals of the form $p < \mathbf{c}$ and $p > \mathbf{c}$.

The idea of interval terms comes from a logic first introduced by (Pavelka 1979a; Pavelka 1979b; Pavelka 1979c) as an extension of $\mathcal{L}$ with constants for every real number. It turns out, however, (cf. (Hájek 1998, §3.3) for details) that if one adds constants only for rational numbers, the resulting logic ('Rational Pavelka logic' or RPL) will have the same expressivity as the original one. To simulate the two-valued behaviour of interval terms, one also needs to introduce the 'Delta operator' $\Delta$ proposed by (Baaz 1996) with the following semantics: $v(\Delta\phi) = 1$ if $v(\phi) = 1$ and $v(\Delta\phi) = 0$, otherwise. Now, using the following equivalences

$$ p \le \mathbf{c} \equiv_{\mathcal{L}} \Delta(p \to \mathbf{c}) \qquad p \ge \mathbf{c} \equiv_{\mathcal{L}} \Delta(\mathbf{c} \to p) $$

$$ p < \mathbf{c} \equiv_{\mathcal{L}} \neg \Delta(\mathbf{c} \to p) \qquad p > \mathbf{c} \equiv_{\mathcal{L}} \neg \Delta(p \to \mathbf{c}) $$

and expanding the constraint tableaux calculus of (Hähnle 1999) with rules for $\Delta$ and rational constants, we have that the satisfiability and validity of $\mathcal{L}^{\mathcal{Q}}$-formulas have the same complexity as those of $\mathcal{L}$.

**Proposition 2.**

1. $\mathcal{L}$-satisfiability of $\mathcal{L}^{\mathcal{Q}}$-formulas is NP-complete.

2. Entailment in $\mathcal{L}$ of $\mathcal{L}^{\mathcal{Q}}$-formulas is coNP-complete.

We note briefly that interval terms allow us to express not only the values of variables but also of arbitrary formulas (cf. (Flaminio 2007) for an alternative approach). For $\phi \in \mathcal{L}_{\mathcal{L}}$ and $p \in \text{Pr s.t. } p \notin \text{Pr}(\phi)$, $c \in [0, 1]_{\mathcal{Q}}$, and $\diamond \in \{\le, <, \ge, >\}$, we have $v(\phi) \diamond c$ iff $v((\phi \leftrightarrow p) \odot p \diamond c) = 1$.

We finish the section by establishing the complexity of the entailment of interval terms.

**Proposition 3.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{\mathcal{L}}^{\mathcal{Q}}$ be finite and $\tau$ and $\tau'$ be interval terms. Then the following statements hold.

1. It takes polynomial time to decide whether $\tau \models_{\mathcal{L}} \tau'$.

2. It is coNP-complete to decide whether $\tau \models_{\mathcal{L}} \chi$.

3. It is coNP-complete to decide $\Gamma, \tau \models_{\mathcal{L}} \tau'$.

# 4 Abduction in Łukasiewicz Logic

Let us now present abduction in $\mathcal{L}$. Our idea is to use interval terms as solutions to problems $\mathbb{P} = \langle\Gamma, \chi, \mathbb{H}\rangle$. Here, $\mathbb{H}$ is the set of hypotheses (interval literals) that one can use to

build solutions. One can restrict it in two ways. First, one may allow arbitrary interval literals over a given finite set of variables. Second, one can explicitly define a finite set of interval literals. We choose the second option, as the first one leads to infinite sets of solutions (cf. Example 1).

**Definition 4** ($\mathcal{L}$-abduction problems and solutions).

* An $\mathcal{L}$-abduction problem is a tuple $\mathbb{P} = \langle\Gamma, \chi, \mathbb{H}\rangle$ with $\Gamma \cup \{\chi\}$ a finite set of $\mathcal{L}^{\mathcal{Q}}$-formulas, and $\mathbb{H}$ a finite set of interval literals. We call $\Gamma$ a theory, $\chi$ an observation, and members of $\mathbb{H}$ hypotheses.

* An $\mathcal{L}$-solution of $\mathbb{P}$ is an interval term $\tau$ composed of hypotheses s.t. $\Gamma, \tau \models_{\mathcal{L}}^{\text{cons}} \chi$.

* A solution is proper if $\tau \nvDash_{\mathcal{L}} \chi$.

* A proper solution $\tau$ is $\models_{\mathcal{L}}$-minimal (entailment-minimal) if there is no proper solution $\sigma$ s.t. $\tau \models_{\mathcal{L}} \sigma$ and $\sigma \nvDash_{\mathcal{L}} \tau$.

* A proper solution $\tau$ is theory-minimal if there is no proper solution $\sigma$ s.t. $\Gamma, \sigma \nvDash_{\mathcal{L}} \tau$ and $\Gamma, \tau \models_{\mathcal{L}} \sigma$.

**Convention 3.** Given an abduction problem $\mathbb{P}$, we will use $S(\mathbb{P})$, $S^{\text{P}}(\mathbb{P})$, $S^{\text{min}}(\mathbb{P})$, and $S^{\text{Th}}(\mathbb{P})$ to denote the sets of all solutions, all proper solutions, all $\models_{\mathcal{L}}$-minimal solutions, and all theory-minimal solutions of $\mathbb{P}$, respectively.

In the definition above, it is evident that there are finitely many (at most exponentially many in the size of $\mathbb{H}$) solutions for each abduction problem. We also present two notions of minimal solutions. Entailment-minimality corresponds to subset-minimality by (Eiter and Gottlob 1995) in the setting of Łukasiewicz logic. Theory-minimal solutions correspond to least specific solutions in the terminology of (Stickel 1990; Sakama and Inoue 1995) and least presumptive solutions in the terminology of (Poole 1989). Theory-minimal solutions can also be seen as duals of theory prime implicates by (Marquis 1995).

In addition, it is easy to see that even though a theory-minimal solution is entailment-minimal, the converse is not always the case. Indeed, let $\mathbb{P} = \langle\{p \vee q, r\}, q \wedge r\rangle$. One can see that there are two entailment-minimal solutions: $p \le \mathbf{0}$ and $q \ge \mathbf{1}$. Note, however, that $p \vee q, r, p \le \mathbf{0} \models_{\mathcal{L}} q \ge \mathbf{1}$. Thus, $p \le \mathbf{0}$ is not theory-minimal.

Let us now see how we can solve abduction problems using interval terms. Recall Example 1.

**Example 2.** We continue Example 1. We need to formulate an abduction problem $\mathbb{P}_{\text{lift}} = \langle\Gamma_{\text{lift}}, \chi_{\text{lift}}, \mathbb{H}_{\text{lift}}\rangle$. $\Gamma_{\text{lift}}$ and $\chi_{\text{lift}}$ are already given in Example 1. It remains to form the set of hypotheses we are allowed to use. Assume for simplicity that we can measure the load of our lift in twelfths of its capacity. Thus, we can set

$$ \mathbb{H}_{\text{lift}} = \{c \diamond \frac{i}{12} \mid \diamond \in \{\le, \ge, <, >\} \text{ and } i \in \{0, \dots, 12\}\} $$

It is now easy to check that $(c \ge \frac{3}{12}) \odot (c \le \frac{8}{12})$ is indeed the theory-minimal solution of $\mathbb{P}_{\text{lift}}$. Moreover, as expected,

$$ S(\mathbb{P}_{\text{lift}}) = \left\{ \left(c \triangleright \frac{i}{12}\right) \odot \left(c \triangleleft \frac{i'}{12}\right) \mid \begin{array}{l} \triangleleft \in \{\le, <\}, \triangleright \in \{\ge, >\}, \\ i \ge 3, i' \le 8, i < i' \end{array} \right\} \cup \left\{ \left(c \le \frac{i}{12}\right) \odot \left(c \ge \frac{i}{12}\right) \mid 3 \le i \le 8 \right\} $$

That is, given any interval $D \subseteq [\frac{1}{4}, \frac{2}{3}]$, every interval term $\tau$ s.t. $v(\tau) = 1$ iff $v(c) \in D$ is a solution to $\mathbb{P}_{\text{lift}}$.
It is also important to observe that the set of solutions depends not only on the variables in $H$ but on their permitted values as well. Indeed, if in Example 2, we supposed that we can measure the load in tenths of the maximal capacity (i.e., if $H = \{c \diamond \frac{i}{10} | \diamond \in \{\le, \ge, <, >\} \text{ and } i \in \{0, \dots, 10\}\}$), the theory-minimal solution would be $(c \ge \frac{3}{10}) \odot (c \le \frac{6}{10})$. Hence, to test a solution $\tau$ for minimality, we need to calculate the nearest permitted value from the boundary value for every interval literal in $\tau$.

Let us now establish the complexity of abductive reasoning. We will consider three standard tasks:

* **solution recognition** — given a problem $\mathbb{P}$ and an interval term $\tau$, determine whether $\tau$ is a (proper, entailment-minimal, or theory-minimal) solution;

* **solution existence** — given a problem $\mathbb{P}$, determine whether $S(\mathbb{P}) = \emptyset$;

* **relevance and necessity of hypotheses** — given a problem $\mathbb{P}$ and a hypothesis $\lambda$, determine whether there is a solution where it occurs and whether it occurs in all solutions.

In our proofs, we will use reductions from the classical abductive reasoning. In the following definition, we recall the notion of classical abduction problem and solutions. We adapt the definitions from (Eiter and Gottlob 1995) and (Creignou and Zanuttini 2006) for our notation. We use terminology and notation for CPL analogous to ones introduced for Ł, e.g., speaking about CPL-validity and using $\models_{CPL}$ for the classical entailment relation.

**Definition 5.** Let $\mathcal{L}_{CPL}$ be the propositional language over $\{\neg, \wedge, \vee\}$. A classical abduction problem is a tuple $\mathbb{P} = (\Gamma, \chi, H) \text{ s.t. } \Gamma \cup \{\chi\} \subseteq \mathcal{L}_{CPL}$ and $H$ is a set of simple literals.

* A solution of $\mathbb{P}$ is a weak conjunction $\tau$ of literals from $H$ such that $\Gamma, \tau \models_{CPL}^{\text{cons}} \psi$.

* A solution $\tau$ is proper if $\tau \nvdash_{CPL} \psi$.

* A proper solution $\tau$ is $\models_{CPL}$-minimal if there is no proper solution $\phi$ s.t. $\tau \models_{CPL} \phi$ and $\phi \nvDash_{CPL} \tau$.

* A proper solution $\tau$ is theory-minimal if there is no proper solution $\phi$ s.t. $\Gamma, \tau \models_{CPL} \phi$ and $\Gamma, \phi \nvDash_{CPL} \tau$.

We will also need the following technical statement.

**Definition 6.** Let $\phi \in \mathcal{L}_{CPL}$. We define $\phi^\mathbb{L}$ as follows:

$$ 
\begin{aligned}
p^{\mathbb{L}} &= p & (\neg\phi)^{\mathbb{L}} &= \neg\phi^{\mathbb{L}} \\
(\phi \wedge \chi)^{\mathbb{L}} &= \phi^{\mathbb{L}} \odot \chi^{\mathbb{L}} & (\phi \vee \chi)^{\mathbb{L}} &= \phi^{\mathbb{L}} \oplus \chi^{\mathbb{L}}
\end{aligned}
$$

Given $\Gamma \subseteq \mathcal{L}_{CPL}$, we set $\Gamma^{\mathbb{L}} = \{\phi^{\mathbb{L}} | \phi \in \Gamma\}$.

**Proposition 4.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{CPL}$. Then

$$ \Gamma \models_{CPL} \chi \text{ iff } \Gamma^{\mathbb{L}}, \{p \vee \neg p | p \in \text{Pr}[\Gamma \cup \{\chi\}]\} \models_{\mathbb{L}} \chi^{\mathbb{L}} $$

The complexity results from this section are in Table 1.

## 4.1 Solution Recognition

We begin with solution recognition. First, we show that recognition of arbitrary, proper, and entailment-minimal solutions is DP-complete.

**Theorem 1.** Let $\mathbb{P} = (\Gamma, \chi, H)$ be an Ł-abduction problem and $\tau$ an interval term. Then, it is DP-complete to decide whether $\tau \in \mathcal{S}(\mathbb{P})$.

<table><caption>Table 1: Complexity of abductive reasoning problems. Unless specified otherwise, all results are completeness results.</caption><thead><tr><th>Recognition and existence</th><th>Ł</th><th>CPL</th></tr></thead><tbody><tr><td>τ ∈ S(Π)? / τ ∈ S<sup>P</sup>(Π)? / τ ∈ S<sup>min</sup>(Π)?</td><td>DP</td><td>DP</td></tr><tr><td>τ ∈ S<sup>Th</sup>(Π)?</td><td>in Π<sup>P</sup><sub>2</sub></td><td>in Π<sup>P</sup><sub>2</sub></td></tr><tr><td>S(Π) ≠ ∅? / S<sup>P</sup>(Π) ≠ ∅?</td><td>Σ<sup>P</sup><sub>2</sub></td><td>Σ<sup>P</sup><sub>2</sub></td></tr><tr><td>Relevance</td><td>Ł</td><td>CPL</td></tr><tr><td>w.r.t. S(Π), S<sup>P</sup>(Π), S<sup>min</sup>(Π)</td><td>Σ<sup>P</sup><sub>2</sub></td><td>Σ<sup>P</sup><sub>2</sub></td></tr><tr><td>w.r.t. S<sup>Th</sup>(Π)</td><td>in Σ<sup>P</sup><sub>3</sub></td><td>in Σ<sup>P</sup><sub>3</sub></td></tr><tr><td>Necessity</td><td>Ł</td><td>CPL</td></tr><tr><td>w.r.t. S(Π), S<sup>P</sup>(Π), S<sup>min</sup>(Π)</td><td>Π<sup>P</sup><sub>2</sub></td><td>Π<sup>P</sup><sub>2</sub></td></tr><tr><td>w.r.t. S<sup>Th</sup>(Π)</td><td>in Π<sup>P</sup><sub>3</sub></td><td>in Π<sup>P</sup><sub>3</sub></td></tr></tbody></table>

**Proof.** The membership follows immediately from Proposition 2 and the fact that $\tau \in S(\mathbb{P})$ iff $\Gamma, \tau \models_{\mathbb{L}}^{\text{cons}} \chi$. For the hardness, we provide a reduction from the classical solution recognition which is DP-complete (Eiter and Gottlob 1995, §4). Let now $\mathbb{P}_{cl} = (\Delta, \psi, H^{cl})$ be a classical abduction problem. Define $\mathbb{P}^{\mathbb{L}} = (\Delta^{\mathbb{L}}, \psi^{\mathbb{L}}, H^{\mathbb{L}})$ as follows:

$$ 
\begin{aligned}
\Delta^{\mathbb{L}} &= \Delta^{\mathbb{L}} \cup \{p \vee \neg p | p \in \text{Pr}[\Delta \cup \{\psi\}]\} \\
H^{\mathbb{L}} &= \{p \ge \mathbf{1} | p \in H^{cl}\} \cup \{q \le \mathbf{0} | q \in H^{cl}\}
\end{aligned}
$$

Furthermore, for $\tau = \bigwedge_{i=1}^m p_i \wedge \bigwedge_{j=1}^n \neg q_j$, we define $\tau^{\odot} = \bigodot_{i=1}^m (p_i \ge \mathbf{1}) \odot \bigodot_{j=1}^n (q_j \le \mathbf{0})$ and show that $\tau \in S(\mathbb{P}_{cl})$ iff $\tau^{\odot} \in S(\mathbb{P}^{\mathbb{L}})$.

Assume that $\tau \in S(\mathbb{P}_{cl})$, i.e., $\Delta, \tau \models_{CPL}^{\text{cons}} \psi$ and let $v$ be a classical valuation s.t. $v(\phi) = 1$ for every $\phi \in \Delta$ and $v(\tau) = 1$. Since $\odot$ and $\oplus$ behave on $\{0, 1\}$ the same as $\wedge$ and $\vee$, it is clear that $v(\chi) = 1$ for every $\chi \in \Delta^{\mathbb{L}}$ and $v(\tau^{\odot}) = 1$ as well. Now assume further for the sake of contradiction that there is some Ł-valuation $v^{\mathbb{L}}$ s.t. $v^{\mathbb{L}}(\chi) = 1$ for every $\chi \in \Delta^{\mathbb{L}}$, $v^{\mathbb{L}}(\tau^{\odot}) = 1$, but $v(\psi^{\mathbb{L}}) \ne 1$. But $v^{\mathbb{L}}$ must be classical, i.e., assign only values from $\{0, 1\}$ to all $p \in \text{Pr}[\Delta \cup \{\psi\}]$ because $p \vee \neg p \in \Delta^{\mathbb{L}}$ and $v^{\mathbb{L}}(p \vee \neg p) = 1$ iff $v(p) \in \{0, 1\}$. This would mean that $v^{\mathbb{L}}$ witnesses $\Delta, \tau \nvDash_{CPL} \psi$, contrary to the assumption.

For the converse direction, given an interval term $\tau$, define $\tau_{cl} = \bigwedge_{p \ge 1 \in \tau} p \wedge \bigwedge_{q \le 0 \in \tau} \neg q$. One can check that $\tau \in S(\mathbb{P}^{\mathbb{L}})$ iff $\tau_{cl} \in S(\mathbb{P})$. $\square$

**Theorem 2.** Let $\mathbb{P} = (\Gamma, \chi, H)$ be an Ł-abduction problem and $\tau$ an interval term. Then, it is DP-complete to decide whether $\tau \in S(\mathbb{P})$.

**Proof.** First, we obtain the hardness via a reduction from the arbitrary solution recognition in Łukasiewicz logic. Namely, let $\mathbb{P} = (\Gamma, \chi, H)$ be an Ł-abduction problem. We show that $\tau \in S(\mathbb{P})$ iff $\tau$ is a proper solution of $\mathbb{P}_p = (\Gamma \cup \{p\}, \chi, \odot, p, H)$ with $p \notin \text{Pr}[\Gamma \cup \{\chi\}]$. Assume that $\tau \in S(\mathbb{P})$. As $p \notin \text{Pr}(\chi)$ and $\tau$ is Ł-satisfiable, it is clear that $\tau \nvDash_{\mathbb{L}} \chi \odot p$. It is also clear that $\Gamma, p, \tau \models_{\mathbb{L}} \perp$ iff $\Gamma, \tau \models_{\mathbb{L}} \perp$ and
$\Gamma, p, \tau \models_{\mathcal{L}} \chi \odot p$ iff $\Gamma, \tau \models_{\mathcal{L}} \chi$. Conversely, let $\tau \in \mathcal{S}^{\mathcal{P}}(\mathbb{P}_p)$. As $\Gamma, p, \tau \models_{\mathcal{L}}^{\text{cons}} \chi$, it is clear that $\Gamma, \tau \models_{\mathcal{L}}^{\text{cons}} \chi$.

For the membership, given $\tau$ and $\mathbb{P}$, we (i) use an NP oracle to guess two $\mathcal{L}$-valuations $v_{\text{sat}}$ and $v_{\text{prp}}$ and check that they witness $\Gamma, \tau \not\models_{\mathcal{L}} \perp$ and $\tau \not\models_{\mathcal{L}} \chi$. At the same time, we (ii) conduct a coNP check that $\Gamma, \tau \models_{\mathcal{L}} \chi$. Note that this is possible because we do not need the result of (i) to do (ii). It follows that $\tau \in \mathcal{S}^{\mathcal{P}}(\mathbb{P})$ iff both checks succeed. $\square$

**Theorem 3.** Let $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$ be an $\mathcal{L}$-abduction problem and $\tau$ an interval term. Then, it is DP-complete to decide whether $\tau \in \mathcal{S}^{\text{min}}(\mathbb{P})$.

*Proof sketch.* We begin with the hardness. We will provide a reduction from the prime implicant recognition in classical logic which is DP-complete (Marquis 2000, Proposition 111). Let w.l.o.g. $\chi$ be classically satisfiable. We can prove that $\tau$ is a prime implicant of $\chi$ iff $\tau^{\odot}$ is an $\models_{\mathcal{L}}$-minimal solution to $\mathbb{P} = (\Gamma, \chi^{\mathcal{L}} \odot q, \mathbb{H})$ with $q \notin \text{Pr}(\chi)$ and

$$ \Gamma = \{p \lor \neg p \mid p \in \text{Pr}(\chi \land q)\} \cup \{q\} \\ H = \{p \geq \mathbf{1} \mid p \in \text{Pr}(\chi)\} \cup \{p \leq \mathbf{0} \mid p \in \text{Pr}(\chi)\} $$

To show this, we use that $v(p \lor \neg p) = 1$ iff $v(p) \in \{0, 1\}$, $v(\tau) \in \{0, 1\}$ for every interval term $\tau$ and $\mathcal{L}$-valuation $v$, and $\neg$, $\odot$, and $\oplus$ behave classically on $\{0, 1\}$. Conversely, given $\tau \in \mathcal{S}^{\text{min}}(\mathbb{P})$, we can define a prime implicant $\tau_{\text{cl}}$ by replacing $\odot$ with $\land$, $r \ge \mathbf{1}$ with $r$, and $s \le \mathbf{0}$ with $\neg s$. The reasoning is similar.

The proof of the membership utilises the fact that given an interval term $\tau = \lambda \odot \tau'$ with $\lambda = p \diamond c$ and a set of hypotheses $H$, there are $\mathcal{O}(|H|)$ interval terms $\sigma$ for which we need to check that $\tau \models_{\mathcal{L}} \sigma$ and $\sigma \not\models_{\mathcal{L}} \tau$ hold. Namely, we can either replace $\lambda$ with the 'next weakest' literal $\lambda^{\mathcal{b}}_{H}$ or (if $\lambda$ is itself the weakest in $H$) remove $\lambda$ altogether. For example, if $H = \{p \diamond_i/4 \mid \Diamond \in \{\le, <, \ge, >\}, i \in \{0, \dots, 4\}\}$ and $\lambda = p \le 1/4$, then $\lambda^{\mathcal{b}}_{H} = p \le 2/4$. Let us now use $\tau^{\mathcal{b}}_{\lambda}$ to denote the term obtained from $\tau$ by replacing $\lambda$ with $\lambda^{\mathcal{b}}_{H}$ or removing $\lambda$ when $\lambda^{\mathcal{b}}_{H} \notin H$. As $\tau \models_{\mathcal{L}} \tau^{\mathcal{b}}_{\lambda}$, $\Gamma, \tau \not\models_{\mathcal{L}} \perp$ entails $\Gamma, \tau^{\mathcal{b}}_{\lambda} \not\models_{\mathcal{L}} \perp$ and $\tau \not\models_{\mathcal{L}} \chi$ entails $\tau^{\mathcal{b}}_{\lambda} \not\models_{\mathcal{L}} \chi$.

Now, we use an NP-oracle that guesses linearly many w.r.t. $|H|$ $\mathcal{L}$-valuations $v_{\text{sat}}$, $v_{\text{prp}}$, and $v_{\lambda}$ (for each $\lambda \in \tau$) and verifies whether they witness (i) $\Gamma, \tau \not\models_{\mathcal{L}} \perp$, (ii) $\tau \models_{\mathcal{L}} \chi$, and (iii) $\Gamma, \tau^{\mathcal{b}}_{\lambda} \not\models_{\mathcal{L}} \chi$. Parallel to that (as we do not need the results of (i)-(iii)), we conduct a coNP check that (iv) $\Gamma, \tau \models_{\mathcal{L}} \chi$. It follows from the definition of $\models_{\mathcal{L}}$-minimal solutions that $\tau$ is a $\models_{\mathcal{L}}$-minimal solution iff the NP and coNP checks succeed. $\square$

In the case of theory-minimal solutions, we establish membership in $\Pi_2^{\mathbb{P}}$. We expect that this case is indeed harder than entailment-minimality, intuitively because the presence of the theory means we cannot readily identify a polynomial number of candidates for better solutions to check. We leave the search for a matching lower bound for future work and remark that, to the best of our knowledge, the complexity of the analogous problem in CPL is also unknown.

**Theorem 4.** It is in $\Pi_2^{\mathbb{P}}$ to decide, given an $\mathcal{L}$-abduction problem $\mathbb{P}$ and an interval term $\tau$, whether $\tau$ is a theory-minimal solution of $\mathbb{P}$.

## 4.2 Solution Existence

We now turn to establishing the complexity of the solution existence in $\mathcal{L}$-abduction problems. Note that a problem may have solutions but no proper solutions. On the other hand, if a problem has proper solutions, it will have entailment- and theory-minimal solutions as well. Thus, we will consider the complexity of arbitrary and proper solution existence.

**Theorem 5.** It is $\Sigma_2^{\mathbb{P}}$-complete to decide whether an $\mathcal{L}$-abduction problem has a (proper) solution.

*Proof.* Membership follows immediately from Theorem 1. For hardness, we provide a reduction from the solution existence for classical abduction problems $\mathbb{P}_{\text{cl}} = (\Gamma_{\text{cl}}, \chi_{\text{cl}}, \mathbb{H})$ of the following form (below $\phi \in \mathcal{L}_{\text{CPL}}$):<fnref n="1" />

$$ \Gamma_{\text{cl}} = \{\neg \phi \lor (p \land \tau), \neg p \lor \tau\} \cup \{\neg r \Leftrightarrow r' \mid r \in \text{Pr}(\phi) \land \text{Pr}(p \land \tau)\} \\ (p \notin \text{Pr}(\phi \land \tau), \tau \text{ is a weak conjunction of literals}) $$

$$ \chi_{\text{cl}} = p \land \tau \\ H = \{r \mid r \in \text{Pr}(\phi) \land \text{Pr}(p \land \tau)\} \cup \{r' \mid \neg r \Leftrightarrow r' \in \Gamma_{\text{cl}}\} \quad (4) $$

By (Eiter and Gottlob 1995, Theorem 4.2), determining the existence of classical solutions for these problems is $\Sigma_2^{\mathbb{P}}$-hard. We reduce $\mathbb{P}_{\text{cl}}$ to $\mathbb{P}^{\mathcal{L}} = (\Gamma^{\mathcal{L}}, \chi_{\text{cl}}^{\mathcal{L}}, \mathbb{H}^{\mathcal{L}})$ as was done in Theorem 1 (recall Definition 6 for $\Gamma^{\mathcal{L}}$ and $\chi^{\mathcal{L}}$) with

$$ \Gamma^{\mathcal{L}} = \Gamma^{\mathcal{L}} \cup \{p \lor \neg p \mid p \in \text{Pr}[\Gamma_{\text{cl}} \cup \{\chi_{\text{cl}}\}]\} \\ H^{\mathcal{L}} = \{s \ge \mathbf{1} \mid s \in \mathbb{H}\} \quad \chi_{\text{cl}}^{\mathcal{L}} = p \odot \bigcirc_{l \in \tau} l \quad (5) $$

First let $\sigma$ be a solution of $\mathbb{P}_{\text{cl}}$. It is immediate from (4) that $\sigma$ is a proper solution because we cannot use variables occurring in $\chi_{\text{cl}}$. It now follows from Proposition 4 that $\Gamma^{\mathcal{L}}, \sigma^{\mathcal{L}} \models_{\mathcal{L}}^{\text{cons}} \chi_{\text{cl}}^{\mathcal{L}}$. Furthermore, as $\sigma \not\models_{\text{CPL}} \chi_{\text{cl}}$, it is clear that $\sigma^{\mathcal{L}} \not\models_{\mathcal{L}} \chi_{\text{cl}}^{\mathcal{L}}$. We can now define $\sigma^{\mathcal{L}} \models = \bigcirc_{s \in \text{Pr}(\sigma)} (s \ge \mathbf{1})$. Using Remark 1, one sees that $\sigma^{\mathcal{L}} \models \mathcal{L} \simeq \chi^{\mathcal{L}}$. Thus, $\sigma^{\mathcal{L}}$ is a (proper) solution of $\mathbb{P}^{\mathcal{L}}$.

Conversely, let $\sigma'$ be a solution of $\mathbb{P}^{\mathcal{L}}$. It is clear that $\sigma' \not\models_{\mathcal{L}} \chi_{\text{cl}}^{\mathcal{L}}$ because $\text{Pr}(\chi_{\text{cl}}^{\mathcal{L}}) \cap \text{Pr}[\mathbb{H}^{\mathcal{L}}] = \emptyset$, and $\chi_{\text{cl}}^{\mathcal{L}}$ is not $\mathcal{L}$-valid. Hence, $\sigma'$ is a proper solution. Define $\sigma'^{\text{cl}} = \bigwedge_{s \in \text{Pr}(\sigma')} s$. We show that $\sigma'^{\text{cl}}$ is a proper solution of $\mathbb{P}_{\text{cl}}$. Since $\sigma'$ is a solution, we have $\Gamma^{\mathcal{L}}, \sigma' \models_{\mathcal{L}} \chi_{\text{cl}}^{\mathcal{L}}$. Using Remark 1, we have $\sigma' \simeq_{\mathcal{L}} \bigcirc_{s \in \text{Pr}(\sigma')} s$, whence, it is clear that $\Gamma^{\mathcal{L}}, \bigcirc_{s \in \text{Pr}(\sigma')} s \models_{\mathcal{L}}^{\text{cons}} \chi_{\text{cl}}^{\mathcal{L}}$, whence, by Proposition 4, $\Gamma, \sigma'^{\text{cl}} \models_{\text{CPL}}^{\text{cons}} \chi_{\text{cl}}$, as required. $\square$

## 4.3 Relevance and Necessity of Hypotheses

Let us now consider the complexity of determining the relevance and necessity of hypotheses w.r.t. solutions to $\mathcal{L}$-abduction problems. Namely, given an $\mathcal{L}$-abduction problem $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$, we will consider the complexity of determining whether an interval literal $\lambda \in \mathbb{H}$ is relevant (necessary) w.r.t. $\mathcal{S}(\mathbb{P})$, $\mathcal{S}^{\mathbb{P}}(\mathbb{P})$, $\mathcal{S}^{\text{min}}(\mathbb{P})$, and $\mathcal{S}^{\text{Th}}(\mathbb{P})$.

We begin with the complexity of relevance and necessity w.r.t. arbitrary, proper, and $\models_{\mathcal{L}}$-minimal solutions. The classical counterparts of these decision problems were considered by (Eiter and Gottlob 1995). We show that the complexity of relevance and necessity w.r.t. (proper) solutions

<footnote n="1">¹We write $\neg r \Leftrightarrow r'$ as a shorthand for $(r \land \neg r') \lor (\neg r \land r')$.</footnote>
and $|\mathcal{L}$-minimal solutions coincides with the complexity of the analogous problems for ($\subseteq$-minimal) solutions in CPL.

**Theorem 6.** It is $\Sigma_2^\mathbb{P}$-complete (resp. $\Pi_2^\mathbb{P}$-complete) to decide, given a $\mathcal{L}$-abduction problem $\mathbb{P} = (\Gamma, \chi, H)$ and $\lambda \in \mathbb{H}$, whether $\lambda$ is relevant (resp. necessary) w.r.t. $\mathcal{S}(\mathbb{P})$. The same holds for relevance and necessity w.r.t. $\mathcal{S}^\mathbb{P}(\mathbb{P})$ and $\mathcal{S}^{\min}(\mathbb{P})$.

**Proof.** The membership is evident from Theorems 1 and 3 as we can just guess a (proper or $\mathcal{L}$-minimal) solution $\tau$ which can be verified in DP time and then check in linear time whether $\lambda \in \tau$. For the hardness, we adapt the proof by (Eiter and Gottlob 1995) and establish a reduction from the solution existence in Łukasiewicz logic. Now let $\mathbb{P} = (\Gamma, \chi, H)$, pick three fresh variables $t$, $t'$, and $t''$, and $\mathbb{P}^r = (\Gamma^r, \chi^r, H^r)$ be as follows:

$$ \begin{aligned} \Gamma^r &= \{t \to \psi \mid \psi \in \Gamma\} \cup \{t' \to \chi, t \to \neg t', t \to t'', t' \to t''\} \\ \chi^r &= t'' \odot \chi \quad H^r = H \cup \{t \ge \mathbf{1}, t' \ge \mathbf{1}\} \end{aligned} \quad (6) $$

Now let $\mathcal{S}^\mathbb{P}(\mathbb{P})$ be the set of all proper solutions of $\mathbb{P}$. It is clear that $\mathcal{S}^\mathbb{P}(\mathbb{P}^r) = \mathcal{S}(\mathbb{P}^r)$ (because $t'' \notin \mathbb{H}^r$) and

$$ \mathcal{S}(\mathbb{P}^r) = \{\varrho \odot (t \ge \mathbf{1}) \mid \varrho \in \mathcal{S}(\mathbb{P}^\mathcal{L})\} \cup \left\{\varrho' \odot (t' \ge \mathbf{1}) \mid \exists H' \subseteq \mathbb{H}: \varrho' = \bigcirc_{l \in \mathbb{H}'} l\right\} $$

and that $\mathbb{P}^\mathcal{L}$ has solutions iff $t$ is relevant and $t'$ is not necessary w.r.t. $\mathcal{S}(\mathbb{P}^r)$.

For hardness w.r.t. $\mathcal{S}^{\min}(\mathbb{P})$, observe that $t$ is relevant to $\mathbb{P}^r$ iff it is relevant w.r.t. $|\mathcal{L}$-minimal solutions. Similarly, $t'$ is (not) necessary in $\mathbb{P}^r$ iff it is (not) necessary w.r.t. $|\mathcal{L}$-minimal solutions. $\square$

We finish the section by presenting the membership results on the complexity of the recognition of relevant and necessary hypotheses w.r.t. theory-minimal solutions. The next statement is an easy consequence of Theorem 4. To the best of our knowledge, no tight complexity bounds have been established for this problem in the CPL-abduction.

**Theorem 7.** It is in $\Sigma_3^\mathbb{P}$ (resp. $\Pi_3^\mathbb{P}$) to decide, given an $\mathcal{L}$-abduction problem $\mathbb{P} = (\Gamma, \chi, H)$ and $\lambda \in \mathbb{H}$, whether $\lambda$ is relevant (resp. necessary) w.r.t. $\mathcal{S}^{\mathbb{H}}(\mathbb{P})$.

# 5 Abduction in Clause Fragments

Recall from Proposition 1 that the complexity of Łukasiewicz logic coincides with the complexity of CPL. On the other hand, while every classical formula can be equivalently represented as a set of $\vee$-clauses, $\mathcal{L}_\mathcal{L}$-formulas cannot be transformed into sets of simple clauses. In fact, the simple clause fragment of $\mathcal{L}_\mathcal{L}$ is decidable in linear time (Bofill et al. 2019, Lemma 2).

**Proposition 5.** Let $\Gamma = \{\kappa_1, \dots, \kappa_n\}$ be a finite set of simple clauses. It takes linear time to decide whether there is an $\mathcal{L}$-valuation $v$ s.t. $v(\kappa_i) = 1$ for every $i \in \{1, \dots, n\}$.

We note briefly that due to (1), the following formulas are pairwise strongly equivalent for any $n \in \mathbb{N}$ and $k < n$:

$$ \bigoplus_{i=1}^{n} l_i \quad \neg l_1 \to \bigoplus_{i=2}^{n} l_i \quad \bigcirc_{i=1}^{n-1} \neg l_i \to l_n \quad \bigcirc_{i=1}^{k} \neg l_i \to \bigoplus_{j=n-k}^{n} l_j \quad (7) $$

<table><caption>Table 2: Abduction in clause fragments. Unless specified otherwise, all results are completeness results. SC — simple clause theories; CF — cover-free theories; IC — theories with arbitrary interval clauses; Horn — classical Horn theories. $X \in \{\mathcal{S}, \mathcal{S}^\mathbb{P}, \mathcal{S}^{\min}\}$.</caption><thead><tr><th></th><th>SC</th><th>IC</th><th>CF</th><th>Horn</th></tr></thead><tbody><tr><td>τ ∈ X(P)?</td><td>P</td><td>DP</td><td>P</td><td>P</td></tr><tr><td>τ ∈ S<sup>Th</sup>(P)?</td><td>in coNP</td><td>in Π<sub>2</sub><sup>P</sup></td><td>in coNP</td><td>in coNP</td></tr><tr><td>X(P) ≠ ∅?</td><td>NP</td><td>Σ<sub>2</sub><sup>P</sup></td><td>NP</td><td>NP</td></tr><tr><td>rel. w.r.t. X(P)</td><td>NP</td><td>Σ<sub>2</sub><sup>P</sup></td><td>NP</td><td>NP</td></tr></tbody></table>

**Proposition 5** together with (7) means, in particular, that the satisfiability of logic programming under Łukasiewicz semantics is polynomial independent of whether it contains negation. In classical logic, the complexity of abduction in polynomial fragments is expectedly lower than in general (cf. (Creignou and Zanuttini 2006) for details). Hence, it is instructive to establish whether the complexity of $\mathcal{L}$-abduction will also be lower in a polynomial fragment.

In this section, we will consider the complexity of $\mathcal{L}$-abduction when the theory is a set of $\oplus$-clauses. Namely, we will be dealing with two cases: when all clauses in $\Gamma$ are simple and when clauses can contain interval literals. The results are shown in Table 2.

## 5.1 Simple Clause Fragment

Let us now consider the complexity of abductive reasoning for the simple clause fragment of $\mathcal{L}$. We begin with the definition of simple clause abduction problems.

**Definition 7 (Simple clause abduction).** A simple clause abduction problem (SCA problem) is an $\mathcal{L}$-abduction problem $\mathbb{P} = (\Gamma, \chi, H)$ s.t. $\Gamma$ is a set of simple clauses and interval terms and $\chi$ is an interval clause, simple clause, interval term, or a simple term.

In the definition above, note that $\Gamma$ can contain interval terms. This makes it possible to express constraints on the values of variables. Similarly, different observations correspond to constraints that we explain based on the theory.

First, we show that recognition of arbitrary, proper, and $|\mathcal{L}$-minimal solutions is P-complete.

**Theorem 8.** Let $\mathbb{P} = (\Gamma, \chi, H)$ be an SCA problem, and $\sigma$ an interval term. Then it is P-complete to decide whether $\sigma$ is an arbitrary, proper, or $|\mathcal{L}$-minimal solution.

*Proof sketch.* For the membership, we provide a sketch of the proof for the case of $\chi$ being an interval literal. Other cases can be dealt with in a similar manner. Observe from Definitions 1 and 3 that if $\kappa = \bigoplus_{i=1}^m p_i \oplus \bigoplus_{j=1}^n \neg q_j$ is an interval clause and $\tau = \bigcirc_{i=1}^r (s_i \diamond c_i)$ an interval term, then $v(\kappa) = 1$ iff $\sum_{i=1}^m v(p_i) + \sum_{j=1}^n (1 - v(q_j)) \ge 1$ and $v(\tau) = 1$ iff $v(s_i) \diamond c_i$ for each $i \in \{1, \dots, r\}$. It can now be easily shown that the satisfiability of sets of clauses and interval terms can be reduced to solving systems of linear inequalities over $[0, 1]$. Similarly, entailment of an interval literal from a set $\Gamma$ containing simple clauses and interval terms
can be reduced to verifying that a system of linear inequalities does not have a solution over $[0, 1]$. As both tasks can be done in polynomial time, arbitrary and proper solutions can be recognised in polynomial time. Finally, consider determining whether $\sigma \in S^{\min}(\mathbb{P})$. From Theorem 3, we have that given $\sigma$, we only need to check polynomially many solution candidates, each of which requires polynomial time.

Let us now tackle the hardness. We provide a logspace reduction from (proper, entailment-minimal) solution recognition for classical Horn theories, which is P-complete. Let $\mathbb{P} = (\Gamma, p, H)$ be a classical Horn abduction problem and $p \notin H$, clauses in $\Gamma$ be finite sets of literals, and $\tau \in S(\mathbb{P})$. I.e., $\Gamma \cup \{\tau\}$ is CPL-satisfiable, and there is a unit resolution inference of $\{p\}$ from $\Gamma \cup \{\tau\}$ (i.e., in each application of the resolution rule, at least one premise is a unit clause). Let $\Gamma^{\oplus}$ be the result of replacing each clause $\{l_1, \dots, l_k\}$ in $\Gamma$ with $l_1 \oplus \dots \oplus l_k$; $\tau^{\diamond\mathbf{l}}$ be the result of replacing $\wedge$ with $\odot$, positive literals $r$ in $\tau$ with $r \ge \mathbf{1}$, and negative literals $\neg q$ with $q \le 0$; and $H^{\mathbf{l}}$ be the result of replacing $r$ in $H$ with $r \ge \mathbf{1}$, and $\neg q$ with $q \le 0$. The size of $\mathbb{P}^{\oplus} = (\Gamma^{\oplus}, p, H^{\mathbf{l}})$ is linear in the size of $\mathbb{P}$, and $\Gamma^{\oplus} \cup \{\tau^{\diamond\mathbf{l}}\}$ is $\mathbf{l}$-satisfiable because $\Gamma \cup \{\tau\}$ is CPL-satisfiable. Furthermore, unit resolution is $\mathbf{l}$-sound: if $v(l_1 \oplus \dots \oplus l_k) = 1$ and $v(l_1) = 0$, then $v(l_2 \oplus \dots \oplus l_k) = 1$. Hence, reusing the inference in $\mathbf{l}$, we have $\Gamma^{\oplus} \cup \{\tau^{\diamond\mathbf{l}}\} \models_{\mathbf{l}} p$. Thus, $\tau^{\diamond\mathbf{l}} \in S(\mathbb{P}^{\oplus})$. Conversely, let $\tau$ solve $\mathbb{P}^{\oplus}$, i.e., $\Gamma^{\oplus} \cup \{\tau^{\diamond\mathbf{l}}\} \models_{\mathbf{l}}^{\text{cons}} p$. Let $\tau_{\text{cl}}$ be obtained from $\tau$ by replacing $\odot$ with $\wedge$, $r \ge \mathbf{1}$ with $r$, and $q \le 0$ with $\neg q$. Clearly, $\Gamma, \tau_{\text{cl}} \models_{\text{CPL}} \bot$. Then there is a classical unit resolution inference of the empty clause from $\Gamma \cup \{\tau_{\text{cl}}\}$. As it is sound in $\mathbf{l}$, $\Gamma, \tau_{\text{cl}} \models_{\mathbf{l}} \bot$. Contradiction.

Observe that all solutions of $\mathbb{P}$ and $\mathbb{P}^{\oplus}$ are proper because $p$ does not occur in them. Thus, our reduction can be used to show that determining the existence of proper solutions is P-hard as well. For the P-hardness of $\models_{\mathbf{l}}$-minimal solution recognition, one can check that if $\tau \in S^{\min}(\mathbb{P})$, then $\tau^{\diamond\mathbf{l}} \in S^{\min}(\mathbb{P}^{\oplus})$. Conversely, if $\sigma \in S^{\min}(\mathbb{P}^{\oplus})$, then $\sigma_{\text{cl}} \in S^{\min}(\mathbb{P})$. $\square$

For the recognition of *theory-minimal* solutions, we provide a coNP membership result.

**Theorem 9.** It is in coNP to decide, given an SCA problem $\mathbb{P}$ and an interval term $\tau$, whether $\tau$ is a theory-minimal solution of $\mathbb{P}$.

As expected, solution existence for simple clause abduction problems is NP-complete.

**Theorem 10.** Given a simple clause abduction problem $\mathbb{P}$, it is NP-complete to decide whether it has (proper) solutions.

*Proof.* The membership is immediate from Theorem 8. For the hardness, we can reuse the reduction from classical Horn abduction given in Theorem 8. $\square$

The NP-completeness of relevance of hypotheses can be obtained using the reduction shown in (6), setting $\chi = p$ and assuming that $\Gamma$ is a set of simple clauses. Indeed, if $\psi$ is a simple clause, then $t \to \psi$ can be represented as a simple clause (recall (7)).

**Theorem 11.** It is NP-complete (resp. coNP-complete) to decide, given an SCA problem $\mathbb{P} = (\Gamma, \chi, H)$ and $\lambda \in H$, whether $\lambda$ is relevant (resp. necessary) w.r.t. $S(\mathbb{P})$. The same holds for relevance and necessity w.r.t. $S^{\text{P}}(\mathbb{P})$ and $S^{\min}(\mathbb{P})$.

We finish the section with two remarks. First, the complexity of simple clause abduction coincides with that of classical Horn abduction (Eiter and Gottlob 1995; Creignou and Zanuttini 2006). Thus, Łukasiewicz abduction with clausal theories is simpler than classical abduction over clausal theories. Second, one can easily see that simple clause abduction problems can be straightforwardly generalised to problems whose theories are Łukasiewicz fuzzy logic programmes as presented by (Vojtáš 1999; Vojtáš 2001) while preserving the complexity.

**Definition 8.** A Łukasiewicz fuzzy logic programme ($\mathbf{l}$-FLP) is a finite set $\Gamma_{\mathbb{P}} = \{\langle \kappa_i, x_i \rangle \mid 1 \le i \le n, x_i \in (0, 1]_{\mathbb{Q}}\}$ with $\kappa_i$'s being simple clauses written as $\bigcirc_{i=1}^{m} l_i \to l$. Pairs $\langle \kappa_i, x_i \rangle$ are called fuzzy rules. An $\mathbf{l}$-valuation $v$ satisfies $\Gamma_{\mathbb{P}}$ if $v(\kappa_i) = x_i$ for every $\langle \kappa_i, x_i \rangle \in \Gamma_{\mathbb{P}}$.

An $\mathbf{l}$-FLP abduction problem is a tuple $\mathbb{P} = (\Gamma_{\mathbb{P}}, \chi, H)$ with $\Gamma_{\mathbb{P}}$ being an $\mathbf{l}$-FLP, $\chi$ a fuzzy rule or interval term, and $H$ a set of interval literals. A solution to $\mathbb{P}$ is defined as in Definition 4.

One can observe from Definition 7 that simple clause abduction problems are a particular case of $\mathbf{l}$-FLP abduction problems (namely, when $x_i = 1$ for every $i$). Thus, the hardness results are preserved. For the membership, note that $\mathbf{l}$-FLP abduction problems can be reduced to solving systems of linear inequalities in the same way as simple clause abduction problems.

## 5.2 Interval Clause Fragment

Results in Section 4 show that the complexity of $\mathbf{l}$-abduction in the general case was not affected by whether we allow the use of interval literals in theories or observations (recall from Definition 4 that theories and observations are defined over $\mathcal{L}_{\mathbf{l}}^{\mathbb{Q}}$). Interval literals can also reduce the size and facilitate the understanding (for a human) of an abduction problem while preserving its solutions. E.g., the theory $\Gamma_{\text{lift}}$ of the problem $\mathbb{P}_{\text{lift}}$ from Examples 1 and 2 can be reformulated as follows: $\Gamma_{\text{lift}}^{\mathbb{Q}} = \{(c \ge \frac{1}{4}) \leftrightarrow g, (c \le \frac{2}{3}) \leftrightarrow b\}$. Observe that $(c \ge \frac{1}{4}) \leftrightarrow g$ is weakly equivalent to $(c \oplus c \oplus c \oplus c) \leftrightarrow g$ and $(c \le \frac{2}{3}) \leftrightarrow b$ to $(\neg c \oplus \neg c \oplus \neg c) \leftrightarrow b$. So, for $\mathbb{P}_{\text{lift}}^{\mathbb{Q}} = (\Gamma_{\text{lift}}^{\mathbb{Q}}, g \odot b, H_{\text{lift}}^{\mathbb{Q}})$, we have $S(\mathbb{P}_{\text{lift}}) = S(\mathbb{P}_{\text{lift}}^{\mathbb{Q}})$ (and likewise for other types of solutions). Moreover, using interval literals in $\oplus$-clauses simplifies the presentation of relations between values. E.g., ‘if $v(p) \ge \frac{1}{2}$, then $v(q) \le \frac{3}{4}$’ can be put as $(p \ge \frac{1}{2}) \rightarrow (q \le \frac{3}{4})$.

Thus, one might wonder whether we can permit theories built from interval clauses (recall Definition 3) and preserve the complexity bounds from Section 5.1. As the next statements show, this is not generally the case.

**Theorem 12.** Let $\mathbb{P} = (\Gamma, p, H)$ be an $\mathbf{l}$-abduction problem s.t. $\Gamma$ is a set of interval clauses and $p \in \text{Pr}$. Then, for an interval term $\tau$, it is DP-complete to decide whether $\tau \in S(\mathbb{P})$.
*Proof sketch.* Membership follows from Theorem 1. Hardness can be shown via a reduction from solution recognition. in CPL. Let $\mathbb{P} = \langle \Gamma, \mathcal{P}, \mathcal{H} \rangle$ be a classical abduction problem with $\Gamma$ a set of $\vee$-clauses. We replace all positive literals $r$ occurring in $\mathbb{P}$ with $r \ge 1$ and all negative literals $\neg s$ with $s < 1$. Given $\tau \in \mathcal{S}(\mathbb{P})$, we produce an $\mathcal{L}$-solution by a similar replacement of literals and changing $\wedge$ to $\odot$. Conversely, a classical solution for $\mathbb{P}$ can be obtained from a solution for the $\mathcal{L}$-abduction problem by a reverse replacement. $\square$

The $\Sigma_2^\mathcal{L}$-hardness of solution existence for $\mathcal{L}$-abduction in the interval clause fragment can be obtained by a reduction used in Theorem 12.

**Theorem 13.** Let $\mathbb{P} = \langle \Gamma, \mathcal{L}, \mathcal{H} \rangle$ be an $\mathcal{L}$-abduction problem s.t. $\Gamma$ is a set of interval clauses. Then it is $\Sigma_2^\mathcal{L}$-complete to decide whether there is a (proper) solution to $\mathbb{P}$.

As expected, determining the relevance of $\lambda \in \mathbb{H}$ is $\Sigma_2^\mathcal{L}$-hard. The next statement can be obtained by a reduction shown in (6). The only difference is that instead of variables $t, t', t''$, we take interval literals $t \ge 1, t' \ge 1$, and $t'' \ge 1$.

**Theorem 14.** It is $\Sigma_2^\mathcal{L}$-complete (resp. $\Pi_2^\mathcal{L}$-complete) to decide, given a $\mathcal{L}$-abduction problem $\mathbb{P} = \langle \Gamma, \chi, \mathcal{H} \rangle$ s.t. $\Gamma$ is a set of interval clauses and $\lambda \in \mathbb{H}$, whether $\lambda$ is relevant (resp. necessary) w.r.t. $\mathcal{S}(\mathbb{P})$. The same holds for relevance and necessity w.r.t. $\mathcal{S}^\mathcal{P}(\mathbb{P})$ and $\mathcal{S}^{\min}(\mathbb{P})$.

Still, we can restrict interval clause theories so that abduction becomes NP-complete. Namely, we prohibit interval literals ‘covering’ the entire $[0, 1]$ interval (e.g., $p \le \frac{2}{3}$ and $p \ge \frac{1}{4}$) in the implicative representation of interval clauses.

**Definition 9.** Let $\Gamma$ be a set of interval clauses represented as $\bigcirc_{i=1}^m (p_i \diamond \mathcal{C}_i) \to (q \diamond \mathcal{D})$ and $\bigcirc_{i=1}^m (p_i \diamond \mathcal{C}_i) \to \bot$. $\Gamma$ is cover-free (CF) if no pair of interval literals $\lambda$ and $\lambda'$ over the same variable occurs in $\Gamma$ s.t. $\mathcal{L} \models \lambda \oplus \lambda'$.

The following theorems can be shown by reductions between Horn abduction problems and $\mathcal{L}$-abduction problems with CF theories.

**Theorem 15.** Let $\mathbb{P} = \langle \Gamma, \tau, \mathcal{H} \rangle$ be an $\mathcal{L}$-abduction problem with $\Gamma$ a CF set of interval clauses and $\tau$ an interval term. Then it is $\mathcal{P}$-complete to check whether an interval term $\sigma$ is a (proper, minimal) solution to $\mathbb{P}$.

**Theorem 16.** Let $\mathbb{P} = \langle \Gamma, \tau, \mathcal{H} \rangle$ be an $\mathcal{L}$-abduction problem with $\Gamma$ a CF set of interval clauses. Then it is NP-complete to decide whether $\mathbb{P}$ has (proper) solutions.

Determining the relevance of hypotheses in CF theories is NP-complete. The proof is the same as for Theorem 14 (but we reduce from hypotheses relevance for Horn theories).

**Theorem 17.** It is NP-complete (resp. coNP-complete) to decide, given an $\mathcal{L}$-abduction problem $\mathbb{P} = \langle \Gamma, \chi, \mathcal{H} \rangle$ with $\Gamma$ being a CF set of interval clauses and $\lambda \in \mathbb{H}$, whether $\lambda$ is relevant (resp. necessary) w.r.t. $\mathcal{S}(\mathbb{P})$. The same holds for relevance and necessity w.r.t. $\mathcal{S}^\mathcal{P}(\mathbb{P})$ and $\mathcal{S}^{\min}(\mathbb{P})$.

The next statement follows from Theorem 15 as for interval terms $\sigma$ and $\tau$ and a CF theory $\Gamma$, it takes polynomial time to check whether $\Gamma, \sigma \models_{\mathcal{L}} \tau$.

**Theorem 18.** Let $\mathbb{P} = \langle \Gamma, \tau, \mathcal{H} \rangle$ be an $\mathcal{L}$-abduction problem with $\Gamma$ a CF theory and $\tau$ an interval term. Then given an interval term $\sigma$, it is in coNP to decide whether $\sigma \in \mathcal{S}^{\text{Th}}(\mathbb{P})$.

# 6 Conclusion and Discussion

We studied abduction in Łukasiewicz logic and its clausal fragments. Our analysis gives an almost complete outline of the complexity of the main decision problems related to abduction (Tables 1 and 2). We established that the complexity of abductive reasoning is never higher than that in CPL (Eiter and Gottlob 1995), (Creignou and Zanuttini 2006), (Pichler and Woltran 2010), (Pfandler, Pichler, and Woltran 2015). Moreover, the complexity of $\mathcal{L}$-abduction in clausal fragment is lower than that of the classical abductive reasoning as long as clauses do not contain interval literals.

Several questions remain open. First, we do not know the exact complexity of theory-minimal solution recognition and relevance in the full language nor its clausal fragments. One way to approach this would be to establish the complexity of the closely related notion of theory prime implicants in CPL and its fragments (Marquis 1995).

It would also be instructive to consider abductive reasoning in fuzzy logics when the entailment is defined via the preservation of the *truth degree* from the premise to the conclusion as proposed by (Bou et al. 2009; Ertola et al. 2015). Indeed, one might not be guaranteed that the statements in the theory are *absolutely true*. Still, in this case, it is reasonable to expect that the observation should be *at least as true* as the theory and the explanation.

Furthermore, (Dubois and Prade 1992), (Poole 1993), (Dubois, Gilio, and Kern-Isberner 2008), and (Sato, Ishihata, and Inoue 2011) have considered abduction in probabilistic and probabilistic contexts. It is also known from (Hájek and Tulipani 2001; Baldi, Cintula, and Noguera 2020) that so-called ‘two-layered’ fuzzy logics can be adapted to reasoning about uncertainty. Thus, it makes sense to explore probabilistic abduction using two-layered logics.

We also note that the context from Example 1 can be represented in abductive constraint logic programming (ACLP) studied by (Kakas, Michael, and Mourlas 2000). It thus makes sense to explore the connection between abduction in fuzzy logic and ACLP.

It is also known that machine learning for visual perception problems is related to abduction (Shanahan 2005; Liang et al. 2022). As fuzzy logic has also found numerous applications in visual perception, it makes sense to explore the applications of abduction in fuzzy logic in this field.

Finally, recall that there are algorithms for solving fuzzy logic abduction problems with fuzzy sets. In our framework, however, a solution corresponds to a set of *intervals* of permitted values of hypotheses. As $\mathcal{L}$-entailment is reducible to *finite-valued Łukasiewicz logics* (Aguzzoli and Ciabattoni 2000), we might hope that it is possible to compute the ‘minimally sufficient’ set of permitted values from the shape of the theory. Thus, it would be instructive to devise algorithms for the generation of solutions in the form of interval terms. As satisfiability and validity in $\mathcal{L}$ are reducible to mixed-integer programming (MIP) (Hähnle 1992; Hähnle 1994), it would make sense to apply MIP solvers. Moreover, since the semantics of $\mathcal{L}$ can be given over *rational numbers* (Esteva et al. 2002), one may try to apply *rational MIP* solvers such as the one by (Cook et al. 2013) as they produce *exact solutions* to mixed-integer problems.
Acknowledgements

The 1st author was supported by JSPS KAKENHI Grant Number JP25K03190 and JST CREST Grant Number JP-MJCR22D3, Japan. We would also like to thank the reviewers for their constructive suggestions and spotting a mistake in the first version of the paper.

References

Aguzzoli, S., and Ciabattoni, A. 2000. Finiteness in infinite-valued lukasiewicz logic. *Journal of Logic, Language and Information* 9(1):5–29.

Baaz, M. 1996. Infinite-valued Gödel logics with 0-1 projections and relativizations. In *Gödel'96: Logical foundations of mathematics, computer science and physics—Kurt Gödel's legacy, Brno, Czech Republic, August 1996, proceedings*. Association for Symbolic Logic. 23–33.

Badreddine, S.; Avila Garcez, A.; Serafini, L.; and Spranger, M. 2022. Logic tensor networks. *Artificial Intelligence* 303(103649):103649.

Baldi, P.; Cintula, P.; and Noguera, C. 2020. Classical and Fuzzy Two-Layered Modal Logics for Uncertainty: Translations and Proof-Theory. *International Journal of Computational Intelligence Systems* 13(1):988–1001.

Bergadano, F.; Cutello, V.; and Gunetti, D. 2000. Abduction in machine learning. In Gabbay, D., and Smets, P., eds., *Abductive Reasoning and Learning*, volume 4 of *Handbook of Defeasible Reasoning and Uncertainty Management Systems*. Dordrecht: Springer Netherlands. 197–229.

Bhagavatula, C.; Le Bras, R.; Malaviya, C.; Sakaguchi, K.; Holtzman, A.; Rashkin, H.; Downey, D.; Yih, W.-t.; and Choi, Y. 2020. Abductive Commonsense Reasoning. In *8th International Conference on Learning Representations, ICLR 2020*. OpenReview.net.

Bofill, M.; Manyà, F.; Vidal, A.; and Villaret, M. 2019. New complexity results for lukasiewicz logic. *Soft Comput.* 23(7):2187–2197.

Borgwardt, S., and Peñaloza, R. 2012. Undecidability of fuzzy description logics. In Brewka, G.; Eiter, T.; and McIlraith, S., eds., *Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference*. AAAI Press.

Borgwardt, S., and Peñaloza, R. 2017. Algorithms for reasoning in very expressive description logics under infinitely valued Gödel semantics. *International Journal of Approximate Reasoning* 83:60–101.

Borgwardt, S.; Distel, F.; and Peñaloza, R. 2014. Gödel description logics with general models. In *DL 2014: Information Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17–20, 2014*, volume 1193, 391–403. CEUR.

Borgwardt, S. 2014. *Fuzzy Description Logics with General Concept Inclusions*. Ph.D. Dissertation, Technische Universität Dresden, Dresden.

Bou, F.; Esteva, F.; Font, J.; Gil, A.; Godo, L.; Torrens, A.; and Verdu, V. 2009. Logics preserving degrees of truth

from varieties of residuated lattices. *Journal of Logic and Computation* 19(6):1031–1069.

Chakraborty, A.; Konar, A.; Pal, N.; and Jain, L. 2013. Extending the contraposition property of propositional logic for fuzzy abduction. *IEEE Transactions in Fuzzy Systems* 21(4):719–734.

Chen, X.; Hu, Z.; and Sun, Y. 2022. Fuzzy logic based logical query answering on knowledge graphs. In *Proceedings of the 36th AAAI Conference on Artificial Intelligence*, volume 36, 3939–3948. Association for the Advancement of Artificial Intelligence (AAAI).

Cook, W.; Koch, T.; Steffy, D.; and Wolter, K. 2013. A hybrid branch-and-bound approach for exact rational mixed-integer programming. *Mathematical Programming Computation* 5(3):305–344.

Creignou, N., and Zanuttini, B. 2006. A Complete Classification of the Complexity of Propositional Abduction. *SIAM Journal of Computing* 36(1):207–229.

Dai, W.-Z.; Xu, Q.; Yu, Y.; and Zhou, Z.-H. 2019. Bridging machine learning and logical reasoning by abductive learning. *Advances in Neural Information Processing Systems* 32.

d'Allonnes, A.; Akdag, H.; and Bouchon-Meunier, B. 2007. Selecting implications in fuzzy abductive problems. In *2007 IEEE Symposium on Foundations of Computational Intelligence*. IEEE.

Diligenti, M.; Gori, M.; and Saccà, C. 2017. Semantic-based regularization for learning and inference. *Artificial Intelligence* 244:143–165.

Dubois, D., and Prade, H. 1992. Possibilistic Abduction. In *International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems*, 3–12. Springer.

Dubois, D.; Gilio, A.; and Kern-Isberner, G. 2008. Probabilistic Abduction Without Priors. *International Journal of Approximate Reasoning* 47(3):333–351.

Ebrahim, R. 2001. Fuzzy logic programming. *Fuzzy Sets And Systems* 117(2):215–230.

Eiter, T., and Gottlob, G. 1995. The Complexity of Logic-Based Abduction. *Journal of the Association for Computing Machinery* 42(1):3–42.

El Ayeb, B.; Marquis, P.; and Rusinowitch, M. 1993. Preferring diagnoses by abduction. *IEEE Transactions on Systems, Man, and Cybernetics* 23(3):792–808.

Ertola, R.; Esteva, F.; Flaminio, T.; Godo, L.; and Noguera, C. 2015. Paraconsistency properties in degree-preserving fuzzy logics. *Soft Computing* 19:531–546.

Esteva, F.; Gispert, J.; Godo, L.; and Montagna, F. 2002. On the Standard and Rational Completeness of Some Axiomatic Extensions of the Monoidal T-norm Logic. *Studia Logica* 71(2):199–226.

Flach, P., and Kakas, A., eds. 2000. *Abduction and Induction*, volume 18 of *Applied Logic Series*. Dordrecht, Netherlands: Springer.
Flaminio, T. 2007. NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach. *Archive for Mathematical Logic* 46(3-4):301–319.

Hähnle, R. 1992. A New Translation From Deduction Into Integer Programming. In *International Conference on Artificial Intelligence and Symbolic Mathematical Computing*, 262–275. Springer.

Hähnle, R. 1994. Many-Valued Logic and Mixed Integer Programming. *Annals of Mathematics and Artificial Intelligence* 12(3-4):231–263.

Hähnle, R. 1999. Tableaux for Many-Valued Logics. In D'Agostino, M.; Gabbay, D.; Hähnle, R.; and Posegga, J., eds., *Handbook of Tableaux Methods*, 529–580. Springer-Science+Business Media, B.V.

Hájek, P., and Tulipani, S. 2001. Complexity of fuzzy probability logics. *Fundamenta Informaticae* 45(3):207–213.

Hájek, P. 1998. *Metamathematics of Fuzzy Logic*, volume 4 of *Trends in Logic*. Dordrecht: Springer.

Haniková, Z.; Manyà, F.; and Vidal, A. 2023. The MaxSAT problem in the real-valued MV-algebra. In Ramanayake, R., and Urban, J., eds., *Automated Reasoning with Analytic Tableaux and Related Methods. TABLEAUX 2023*, volume 14278 of *Lecture Notes in Artificial Intelligence*. Cham: Springer Nature Switzerland. 386–404.

Haniková, Z. 2011. Computational Complexity of Propositional Fuzzy Logics. In Cintula, P.; Hájek, P.; and Noguera, C., eds., *Handbook of Mathematical Fuzzy Logic*, volume 38 of *Studies in logic*. College Publications. 793–852.

Inoue, K., and Kozhemiachenko, D. 2025. Complexity of abduction in Łukasiewicz logic. Available at: arXiv: 2507.13847.

Josephson, J., and Josephson, S., eds. 2009. *Abductive inference*. Cambridge, England: Cambridge University Press.

Kakas, A.; Michael, A.; and Mourlas, C. 2000. ACLP: Abductive constraint logic programming. *The Journal of Logic Programming* 44(1-3):129–177.

Koitz-Hristov, R., and Wotawa, F. 2018. Applying algorithm selection to abductive diagnostic reasoning. *Applied Intelligence* 48(11):3976–3994.

Krieken, E. v.; Acar, E.; and Harmelen, F. v. 2022. Analyzing differentiable fuzzy logic operators. *Artificial Intelligence* 302(103602):103602.

Liang, C.; Wang, W.; Zhou, T.; and Yang, Y. 2022. Visual Abductive Reasoning. In *2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*. IEEE.

Magnani, L. 2011. *Abduction, reason and science*. New York, NY: Springer, 2001 edition.

Marquis, P. 1995. Knowledge Compilation Using Theory Prime Implicates. In *Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95)*, volume I, 837–845.

Marquis, P. 2000. Consequence Finding Algorithms. In *Handbook of Defeasible Reasoning and Uncertainty Management Systems: Algorithms for Uncertainty and Defeasible Reasoning*. Springer. 41–145.

McNaughton, R. 1951. A theorem about infinite-valued sentential logic. *The Journal of Symbolic Logic* 16(1):1–13.

Mellouli, N., and Bouchon-Meunier, B. 2003. Abductive reasoning and measures of similitude in the presence of fuzzy rules. *Fuzzy Sets And Systems* 137(1):177–188.

Miyata, Y.; Furuhashi, T.; and Uchikawa, Y. 1998. A proposal of abductive inference with degrees of manifestations. *International Journal of Intelligent Systems* 13(6):467–481.

Mundici, D. 1987. Satisfiability in many-valued sentential logic is NP-complete. *Theoretical Computer Science* 52(1):145–153.

Paul, G. 1993. Approaches to abductive reasoning: an overview. *Artificial Intelligence Review* 7(2):109–152.

Pavelka, J. 1979a. On Fuzzy Logic I. Many-valued rules of inference. *Mathematical Logic Quarterly* 25(3-6):45–52.

Pavelka, J. 1979b. On Fuzzy Logic II. Enriched residuated lattices and semantics of propositional calculi. *Mathematical Logic Quarterly* 25(7-12):119–134.

Pavelka, J. 1979c. On Fuzzy Logic III. Semantical completeness of some many-valued propositional calculi. *Mathematical Logic Quarterly* 25(25-29):447–464.

Pfandler, A.; Pichler, R.; and Woltran, S. 2015. The Complexity of Handling Minimal Solutions in Logic-Based Abduction. *Journal of Logic and Computation* 25(3):805–825.

Pichler, R., and Woltran, S. 2010. The Complexity of Handling minimal Solutions in Logic-Based Abduction. In *Proceedings of 19th European Conference on Artificial Intelligence (ECAI-2010)*, volume 215 of *Frontiers in Artificial Intelligence and Applications*. IOS Press. 895–900.

Poole, D. 1989. Explanation and Prediction: An Architecture for Default and Abductive Reasoning. *Computational Intelligence* 5(2):97–110.

Poole, D. 1993. Probabilistic Horn abduction and Bayesian networks. *Artificial Intelligence* 64(1):81–129.

Rodriguez, R.; Tuyt, O.; Esteva, F.; and Godo, L. 2022. Simplified Kripke semantics for K45-like Gödel modal logics and its axiomatic extensions. *Studia Logica* 110(4):1081–1114.

Sakama, C., and Inoue, K. 1995. The Effect of Partial Deduction in Abductive Reasoning. In *Logic Programming: The 12th International Conference*. The MIT Press.

Sato, T.; Ishihata, M.; and Inoue, K. 2011. Constraint-based probabilistic modeling for statistical abduction. *Machine Learning* 83(2):241–264.

Shanahan, M. 2005. Perception as abduction: turning sensor data into meaningful representation. *Cognitive Science* 29(1):103–134.

Stickel, M. 1990. Rationale and Methods for Abductive Reasoning in Natural-Language Interpretation. In *Natural Language and Logic*, volume 459 of *Lecture Notes in Artificial Intelligence*, 233–252. Springer.

Stoian, M.; Giunchiglia, E.; and Lukasiewicz, T. 2023. Exploiting T-norms for Deep Learning in Autonomous Driving. In *Avila Garcez, A.; Besold, T.; Gori, M.; and Jiménez-Ruiz, E.*, eds., *Proceedings of the 17th International Work-
shop on Neural-Symbolic Learning and Reasoning, NeSy
2023, 369–380.

Straccia, U. 2016. *Foundations of fuzzy logic and semantic web languages*. Chapman & Hall/CRC Studies in Informationics Series. Philadelphia, PA: Chapman & Hall/CRC.

Tsypyschev, V. 2017. Application of risk theory approach to fuzzy abduction. In *Cybernetics and Mathematics Applications in Intelligent Systems*, volume 574 of *Advances in Intelligent Systems and Computing*. Cham: Springer International Publishing. 13–19.

Vojtáš, P. 2001. Fuzzy logic programming. *Fuzzy Sets And Systems* 124(3):361–370.

Vojtáš, P. 1999. Fuzzy Logic Abduction. In Mayor, G., and Suñer, J., eds., *Proceedings of the EUSFLAT-ESTYLF Joint Conference*, 319–322. Universitat de les Illes Balears, Palma de Mallorca, Spain.

Yamada, K., and Mukaidono, M. 1995. Fuzzy Abduction Based on Łukasiewicz Infinite-Valued Logic and Its Approximate Solutions. In *Proceedings of 1995 IEEE International Conference on Fuzzy Systems.*, volume 1, 343–350. IEEE.

Zadeh, L. 1965. Fuzzy sets. *Information and Control* 8(3):338–353.

Zadeh, L. 1975. Fuzzy logic and approximate reasoning. *Synthese* 30(3-4):407–428.
# A Proofs of Section 3

**Proposition 3.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{\mathcal{L}}^{\mathcal{Q}}$ be finite and $\tau$ and $\tau'$ be interval terms. Then the following statements hold.

1. It takes polynomial time to decide whether $\tau \models_{\mathcal{L}} \tau'$.

2. It is coNP-complete to decide whether $\tau \models_{\mathcal{L}} \chi$.

3. It is coNP-complete to decide $\Gamma, \tau \models_{\mathcal{L}} \tau'$.

*Proof.* We begin with Item 1. For an interval literal $\lambda$ over $p \in \text{Pr}$, define

$$ \text{int}(p, p \leq \mathbf{c}) = [0, c] \qquad \text{int}(p, p \geq \mathbf{c}) = [c, 1] $$

$$ \text{int}(p, p < \mathbf{c}) = [0, c) \qquad \text{int}(p, p > \mathbf{c}) = (c, 1] $$

It is clear that $v(\lambda) = 1$ iff $v(p) \in \text{int}(p, \lambda)$ (and $v(\lambda) = 0$, otherwise). Now for an interval term $\sigma$ and $p \in \text{Pr}(\sigma)$, set

$$ \text{int}(p, \sigma) = \bigcap_{\lambda \in \sigma} \text{int}(p, \lambda) $$

One can straightforwardly verify that $\sigma$ is $\mathcal{L}$-satisfiable iff $\text{int}(p, \sigma) \neq \emptyset$ for every $p \in \text{Pr}(\sigma)$. Moreover, if $\sigma$ is not satisfiable, then $v(\sigma) = 0$ for every $v$.

Now let $\sigma$ and $\tau$ be two $\mathcal{L}$-satisfiable interval terms. We show that $\sigma \models_{\mathcal{L}} \tau$ iff the following two conditions are met:

(a) $\text{Pr}(\sigma) \supset \text{Pr}(\tau)$;

(b) $\text{int}(p, \tau) \subseteq \text{int}(p, \sigma)$ for every $p \in \text{Pr}(\sigma)$.

Assume that (a) and (b) hold and that $v(\sigma) = 1$. Then, clearly $v(p) \in \text{int}(p, \sigma)$ for every $p \in \text{Pr}(\sigma)$. By (a) and (b), we have $v(p) \in \text{int}(p, \tau)$ for every $p \in \text{Pr}(\tau)$, whence $v(\tau) = 1$.

Conversely, assume that (a) does not hold and that there is some $p \in \text{Pr}(\tau) \setminus \text{Pr}(\sigma)$. Since $\sigma$ is satisfiable, let $v(\sigma) = 1$ and set $v(p) \notin \text{int}(p, \tau)$. It is clear that $v(\tau) = 0$. Now, assume that (b) does not hold, i.e., there is some $p \in \text{Pr}(\sigma)$ s.t. $\text{int}(p, \tau) \not\subseteq \text{int}(p, \sigma)$. Now let $v$ be an $\mathcal{L}$-valuation s.t. $v(\sigma) = 1$ and $v(p) = x$ for some $x \in \text{int}(p, \sigma) \setminus \text{int}(p, \tau)$. It is clear that $v(\tau) = 0$.

Finally, given two interval terms $\sigma$ and $\tau$, one of the three options holds: either $\sigma$ is unsatisfiable (whence, $\sigma \models_{\mathcal{L}} \tau$), $\sigma$ is satisfiable but $\tau$ is not (whence, $\sigma \not\models_{\mathcal{L}} \tau$), or both are satisfiable. As it takes polynomial time to verify whether there is some $p \in \text{Pr}(\sigma)$ or $q \in \text{Pr}(\tau)$ s.t. $\text{int}(p, \sigma) = \emptyset$ or $\text{int}(q, \tau) = \emptyset$, the satisfiability of interval terms can be checked in polynomial time. Finally, for the third case, we need to verify that (a) and (b) hold which can also be done in polynomial time.

For Item 2, the membership is evident from Proposition 2 and hardness can be obtained by the following reduction from $\mathcal{L}$-validity. Namely, $\chi \in \mathcal{L}_{\mathcal{L}}^{\mathcal{Q}}$ is $\mathcal{L}$-valid (i.e., is entailed by the empty set of formulas) iff $p \geq 1 \models_{\mathcal{L}} \chi$ for some $p \notin \text{Pr}(\chi)$.

The hardness part of Item 3 is obtained by the reduction from $\mathcal{L}$-unsatisfiability. Let $\Gamma = \{\phi\}$. It is clear that $\phi$ is $\mathcal{L}$-unsatisfiable iff $\phi, p \geq 1 \models q \geq 1$ for some $p, q \notin \text{Pr}(\phi)$. The membership follows from Proposition 2. $\square$

# B Proofs of Section 4

**Proposition 4.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{CPL}$. Then

$$ \Gamma \models_{CPL} \chi \text{ iff } \Gamma^{\mathcal{L}} \cup \{p \lor \neg p \mid p \in \text{Pr}[\Gamma \cup \{\chi\}]\} \models_{\mathcal{L}} \chi^{\mathcal{L}} $$

*Proof.* Observe that given an $\mathcal{L}$-valuation $v$, $v(p \lor \neg p) = 1$ iff $v(p) \in \{0, 1\}$. Furthermore, on $\{0, 1\} \odot$ works the same as $\land$ and $\oplus$ as $\lor$ (cf. Definition 1 and (2)). Now let $v$ be a classical valuation witnessing $\Gamma \not\models_{CPL} \chi$. It is clear that $v$ also witnesses $\Gamma^{\mathcal{L}}$, $\{p \lor \neg p \mid p \in \text{Pr}[\Gamma \cup \{\chi\}]\} \not\models_{\mathcal{L}} \chi$. Conversely, let $v$ be an $\mathcal{L}$-valuation witnessing $\Gamma^{\mathcal{L}}$, $\{p \lor \neg p \mid p \in \text{Pr}[\Gamma \cup \{\chi\}]\} \not\models_{\mathcal{L}} \chi$. As we have just observed, this means that all variables are evaluated over $\{0, 1\}$. As $\Gamma^{\mathcal{L}}$ and $\chi^{\mathcal{L}}$ are obtained from $\Gamma$ and $\chi$ by replacing $\land$ and $\lor$ with $\odot$ and $\oplus$, it follows that $\Gamma \not\models_{CPL} \chi$. $\square$

**Definition 10.** Let $\chi \in \mathcal{L}_{CPL}$ and $\tau$ be a weak conjunction of simple literals. We say that $\tau$ is a prime implicant of $\chi$ iff $\tau \models_{CPL} \phi$ and there is no other weak conjunction $\tau'$ of simple literals s.t. $\tau' \models_{CPL} \chi, \tau \models_{CPL} \tau'$, and $\tau' \not\models_{CPL} \tau$.

The next definition introduces 'next weakest literals' given $p \diamond c$ and $H$. The idea is to incrementally extend the interval corresponding to $p \diamond c$.

**Definition 11.** For a finite set of interval literals $H$, $\lambda \in H$, and $c \in [0, 1]_{\mathcal{Q}}$, we define

$$ \mathbf{c}^{\uparrow}(p) = \min \{\mathbf{c}' \in \mathcal{Q} \mid \mathbf{c}' > \mathbf{c} \text{ and } p \leq \mathbf{c}' \in H; \text{ or } p < \mathbf{c}' \in H\} $$

$$ \mathbf{c}^{\downarrow}(p) = \max \{\mathbf{c}' \in \mathcal{Q} \mid \mathbf{c}' < \mathbf{c} \text{ and } p \geq \mathbf{c}' \in H; \text{ or } p > \mathbf{c}' \in H\} $$

Now, let $\mathbf{c}^{\downarrow}(p)$ and $\mathbf{d}^{\uparrow}(p)$ exist in $H$ for $p$. We define:

$$ (p \geq \mathbf{c})_{H}^{\flat} = \begin{cases} p \geq \mathbf{c}^{\downarrow} & \text{if } p \geq \mathbf{c}^{\downarrow} \in H \\ p > \mathbf{c}^{\downarrow} & \text{otherwise} \end{cases} $$

$$ (p > \mathbf{c})_{H}^{\flat} = \begin{cases} p \geq \mathbf{c} & \text{if } p \geq \mathbf{c} \in H \\ p \geq \mathbf{c}^{\downarrow} & \text{if } p \geq \mathbf{c}^{\downarrow} \in H \\ p > \mathbf{c}^{\downarrow} & \text{otherwise} \end{cases} $$

$$ (p \leq \mathbf{d})_{H}^{\flat} = \begin{cases} p \leq \mathbf{d}^{\uparrow} & \text{if } p \geq \mathbf{d}^{\uparrow} \in H \\ p > \mathbf{d}^{\uparrow} & \text{otherwise} \end{cases} $$

$$ (p < \mathbf{d})_{H}^{\flat} = \begin{cases} p \leq \mathbf{d} & \text{if } p \leq \mathbf{d} \in H \\ p \leq \mathbf{d}^{\uparrow} & \text{if } p \leq \mathbf{d}^{\uparrow} \in H \\ p < \mathbf{d}^{\uparrow} & \text{otherwise} \end{cases} $$

**Theorem 3.** Let $\mathbb{P} = (\Gamma, \chi, H)$ be an $\mathcal{L}$-abduction problem and $\tau$ an interval term. Then, it is DP-complete to decide whether $\tau \in \mathcal{S}^{\min}(\mathbb{P})$.

*Proof.* For the hardness, we provide a reduction from the prime implicant recognition in classical logic which is known to be DP-complete (Marquis 2000, Proposition 111). Let w.l.o.g. $\chi$ be classically satisfiable and $\tau$ a prime implicant of $\chi$. Thus, $\tau \models_{CPL}^{\text{cons}} \chi$ and there is no weak conjunction of simple literals $\sigma$ s.t. $\sigma \models_{CPL}^{\text{cons}} \chi, \tau \models_{CPL} \sigma$, and $\sigma \not\models_{CPL} \tau$. We show that $\tau^{\odot}$ is an $\mathcal{L}$-minimal solution to $\mathbb{P} = (\Gamma, \chi^{\mathcal{L}} \odot q, H)$ with $q \notin \text{Pr}(\chi)$ and

$$ \Gamma = \{p \lor \neg p \mid p \in \text{Pr}(\chi \land q)\} \cup \{q\} $$

$$ H = \{p \geq 1 \mid p \in \text{Pr}(\chi)\} \cup \{p \leq 0 \mid p \in \text{Pr}(\chi)\} $$

First, it is clear that all solutions of $\mathbb{P}$ are proper because $q$ does not occur in $H$. Now, consider $\tau^{\odot}$. It is clear that $\Gamma, \tau^{\odot} \models_{\mathcal{L}}^{\text{cons}} \chi^{\mathcal{L}} \odot q$. Indeed, $\tau$ was classically satisfiable,
whence $\tau^{\circ}$ is $\mathcal{L}$-satisfiable by the same valuation $v$ that satisfied $\tau$ since $\odot$ and $\wedge$ behave identically on $\{0, 1\}$. But it also means that $\Gamma \cup \{\tau\}$ is $\mathcal{L}$-satisfiable as $v(p \vee \neg p) = 1$ iff $v(p) \in \{0, 1\}$ and we can set $v(q) = 1$. Furthermore, if for some $\mathcal{L}$-valuation $v'$, $v'(\tau^{\circ}) = 1$ and $v'(\phi) = 1$ for every $\phi \in \Gamma$, it means that all variables are evaluated over $\{0, 1\}$, i.e., $v'$ is a classical valuation. Hence, $v'(\chi^{\circ} \odot q) = 1$, as required. It remains to see that there is no solution $\sigma$ s.t. $\tau^{\circ} \models_{\mathcal{L}} \sigma$ and $\sigma \not\models_{\mathcal{L}} \tau^{\circ}$. Assume for the sake of contradiction that there is such a solution $\sigma$ and define

$$ \sigma^{\text{cl}} = \bigwedge_{p \ge 1 \in \sigma} p \wedge \bigwedge_{r \le 0 \in \sigma} \neg r $$

We will show that $\sigma^{\text{cl}} \not\models_{\text{CPL}} \tau$, $\sigma^{\text{cl}} \models_{\text{CPL}} \chi$, and $\tau \models_{\text{CPL}} \sigma^{\text{cl}}$. Observe that $(\sigma^{\text{cl}})^{\circ} = \sigma$. Now, let $v$ be an $\mathcal{L}$-valuation witnessing $\sigma \not\models_{\mathcal{L}} \tau^{\circ}$. Since $\sigma$ and $\tau^{\circ}$ are interval terms containing only literals of the form $r \le 0$ and $r \ge 1$, it means that $v(\sigma) = 1$ and $v(\tau^{\circ}) = 0$. Now, we define a classical valuation $v^{\text{cl}}$ as follows:

$$ v^{\text{cl}}(r) = \begin{cases} 1 & \text{if } v(s \ge \mathbf{1}) = 1 \text{ or } v(r \le 0) = 0 \\ 0 & \text{if } v(r \le 0) = 1 \text{ or } v(r \ge \mathbf{1}) = 0 \end{cases} $$

It is clear that $v^{\text{cl}}$ witnesses $\sigma^{\text{cl}} \not\models_{\text{CPL}} \tau$. Finally, using the definition of $\Gamma$, that $\sigma$ contains only literals of the form $r \le 0$ and $r \ge 1$, and that all $\mathcal{L}_{\mathcal{L}}$ connectives behave classically on $\{0, 1\}$, we obtain that $\Gamma, \sigma \models_{\mathcal{L}}^{\text{cons}} \chi \odot q$ entails $\sigma^{\text{cl}} \models_{\text{CPL}} \chi$ and $\tau^{\circ} \models_{\mathcal{L}} \sigma$ entails $\tau \models_{\text{CPL}} \sigma^{\text{cl}}$. This, however, means that $\tau$ is not a prime implicant of $\chi$, contrary to the assumption.

For the converse, let $\tau \in S^{\min}(\mathbb{P})$. Define $\tau_{\text{cl}} = \bigwedge_{(r \ge 1) \in \tau} r \wedge \bigwedge_{(s \le 0) \in \tau} \neg s$. From Proposition 4 and the fact that $\tau \simeq_{\mathcal{L}} \bigwedge_{(r \ge 1) \in \tau} r \odot \bigwedge_{(s \le 0) \in \tau} \neg s$, we have $\tau_{\text{cl}} \models_{\mathcal{L}}^{\text{cons}} \chi$. Now assume for contradiction that there is some $\sigma$ s.t. $\sigma \models_{\text{CPL}} \chi$, $\tau \models_{\text{CPL}} \sigma$, but $\sigma \not\models_{\text{CPL}} \tau$. It is easy to check that in this case, $\sigma^{\circ} \in S(\mathbb{P})$, $\tau \models_{\mathcal{L}} \sigma^{\circ}$, and $\sigma^{\circ} \not\models_{\mathcal{L}} \tau$, i.e., $\tau$ is not a $\mathcal{L}$-minimal solution, contrary to the assumption.

Now, consider the membership. Given $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$, $\tau = \bigcirc_{i=1}^{n} \lambda_i$, and $k \in \{1, \dots, n\}$, let

$$ \tau_{\lambda_k}^{\mathcal{L}} = \begin{cases} \bigodot \lambda' \odot \lambda_{k\mathcal{H}}^{\mathcal{L}} & \text{if } \lambda_{k\mathcal{H}}^{\mathcal{L}} \text{ is defined} \\ \lambda' \in \tau & \\ \lambda' \neq \lambda & \\ k-1 & \\ \bigcirc_{i=1}^{n} \lambda_i \odot \bigcirc_{j=k+1}^{n} \lambda_j & \text{otherwise} \end{cases} $$

We use an NP-oracle to guess $O(|\mathbb{H}|)$ valuations $v_{\text{sat}}$, $v_{\text{prp}}$ and $v_{\lambda}$ (for each $\lambda \in \tau$) and verify whether they witness (i) $\Gamma, \tau \not\models_{\mathcal{L}} \bot$, (ii) $\tau \not\models_{\mathcal{L}} \chi$, and (iii) $\Gamma, \tau_{\lambda}^{\mathcal{L}} \not\models_{\mathcal{L}} \chi$, respectively. Parallel to that (as we do not need the results of (i)-(iii)), we conduct a coNP check that (iv) $\Gamma, \tau \models_{\mathcal{L}} \chi$. It follows from the definition of $\models_{\mathcal{L}}$-minimal solutions that $\tau$ is a $\models_{\mathcal{L}}$-minimal solution iff the NP and coNP checks succeed. $\square$

**Theorem 4.** It is in $\Pi_2^{\mathbb{P}}$ to decide, given an $\mathcal{L}$-abduction problem $\mathbb{P}$ and an interval term $\tau$, whether $\tau$ is a theory-minimal solution of $\mathbb{P}$.

*Proof.* Let $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$ be a $\mathcal{L}$-abduction problem, and $\sigma$ is the interval term we are testing. We sketch a $\Sigma_2^{\mathbb{P}}$ procedure for the complementary problem of testing whether $\sigma$ is not a theory-minimal solution. We first guess either (1) 'not a proper solution' or (2) another interval term $\sigma'$. In the case (1), due to the DP-completeness of proper solution recognition (Theorem 2), we make one or two calls to an NP oracle to verify that $\sigma$ is indeed not a proper solution (in which case we return 'yes'). In the case (2), we can make four calls to an NP oracle: two to verify that $\sigma'$ is a proper solution; one to verify that $\Gamma, \sigma \models_{\mathcal{L}} \sigma'$, and another one to check that $\Gamma, \sigma' \not\models_{\mathcal{L}} \sigma$ (returning 'yes' if the calls show this to be the case). By Proposition 3, these entailments can indeed be verified by an NP-oracle. The procedure we have just described will return yes iff the input $\sigma$ is not a theory-minimal solution, which yields the desired membership in $\Pi_2^{\mathbb{P}}$ for the original problem. $\square$

**Theorem 7.** It is in $\Sigma_3^{\mathbb{P}}$ (resp. $\Pi_3^{\mathbb{P}}$) to decide, given an $\mathcal{L}$-abduction problem $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$ and $\lambda \in \mathbb{H}$, whether $\lambda$ is relevant (resp. necessary) w.r.t. $S^{\text{Th}}(\mathbb{P})$.

*Proof.* We consider the relevance. Recall from Theorem 4 that a theory-minimal solution can be recognised in $\Pi_2^{\mathbb{P}}$. Thus, it suffices to guess a theory-minimal solution $\tau$ and then check that $\lambda$ indeed occurs there. It follows that the relevance of a hypothesis w.r.t. the set of theory-minimal solutions can be decided in $\Sigma_3^{\mathbb{P}}$. In the same way, we can show that non-necessity of a hypothesis can also be decided in $\Sigma_3^{\mathbb{P}}$. Hence, necessity is decidable in $\Pi_3^{\mathbb{P}}$. $\square$

### C Proofs of Section 5

**Definition 12.** Let $\kappa = \bigoplus_{i=1}^{m} p_i \oplus \bigoplus_{j=1}^{n} \neg q_j$ be a simple clause and $\lambda = p \diamond c$ an interval literal. We define linear inequalities $\kappa^{\text{LI}}$ and $\lambda^{\text{LI}}$ as follows:

$$ \kappa^{\text{LI}} = \sum_{i=1}^{m} x_{p_i} + \sum_{j=1}^{n} (1 - x_{q_j}) \geq 1 \qquad \lambda^{\text{LI}} = x_p \diamond c $$

Now let

$$ \Gamma = \{\kappa_i | i \in \{1, \dots, m\}\} \cup \{\tau_j | j \in \{1, \dots, n\}\} $$

be a set containing simple clauses and interval terms s.t. $\tau_j = \bigoplus_{i=1}^{k_j} \lambda_i^j$. We define the system of linear inequalities $\Gamma^{\text{LI}}$ that corresponds to $\Gamma$ as follows:

$$ \Gamma^{\text{LI}} = \{\kappa_i^{\text{LI}} | i \in \{1, \dots, m\}\} \cup \bigcup_{j=1}^{n} \{(\lambda_i^j)^{\text{LI}} | i \in \{1, \dots, k_j\}\} $$

**Theorem 8.** Let $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$ be an SCA problem, and $\sigma$ an interval term. Then it is P-complete to decide whether $\sigma$ is an arbitrary, proper, or $\models_{\mathcal{L}}$-minimal solution.

*Proof.* We provide the remaining details of the membership proof. We assume w.l.o.g. that $\sigma = \bigcirc_{i=1}^{n} \lambda_i$ and that $\chi$ is an interval or a simple clause. Indeed, it is easy to see that explaining a simple or an interval term $\tau = \bigcirc_{i=1}^{m} \lambda'_i$ is
equivalent to explaining all its literals separately. To establish that $\sigma \in S(\mathbb{P})$, we need to check that (i) $\Gamma, \sigma \models_{\mathcal{L}} \perp$ and (ii) $\Gamma, \sigma \models_{\mathcal{L}} \chi$. For (i), observe from Definitions 1 and 12 that $\Gamma \cup \{\sigma\}$ is satisfiable iff $S = \Gamma^{\mathbb{L}} \cup \bigcup_{i=1}^n \{\lambda_i^{\mathbb{L}}\}$ has a solution over $[0, 1]$. For (ii), we have two cases depending on whether $\chi$ is a simple clause or an interval clause.

First, let $\chi = \bigoplus_{i=1}^k p_i \oplus \bigoplus_{i=1}^m \neg q_i$. We have that $\Gamma, \sigma \models_{\mathcal{L}} \chi$ iff $S \cup \{\sum_{i=1}^k x_{p_i} + \sum_{i=1}^m (1 - x_{q_i}) < 1\}$ does not have a solution over $[0, 1]$. Second, if $\chi = \bigoplus_{i=1}^k \lambda'_i$, then $\Gamma, \sigma \models_{\mathcal{L}} \chi$ iff $S \cup \{-\lambda'_i^{\mathbb{L}} | 1 \le i \le k\}$ does not have a solution over $[0, 1]$.

As both (i) and (ii) can be determined in polynomial time, arbitrary solutions can be recognised in polynomial time too. For proper solutions, we need to check that $\sigma \not\models_{\mathcal{L}} \chi$. Again, it is easy to see that this check can also be done in polynomial time. Finally, as entailment between interval terms is decidable in polynomial time (Proposition 3) and as there are only polynomially many candidates for every given interval term (recall the proof of Theorem 3), $\models_{\mathcal{L}}$-minimal solutions are recognisable in polynomial time as well. $\square$

**Theorem 9.** It is in coNP to decide, given an SCA problem $\mathbb{P}$ and an interval term $\tau$, whether $\tau$ is a theory-minimal solution of $\mathbb{P}$.

*Proof.* We consider the complementary problem: given $\tau$ and $\mathbb{P} = (\Gamma, \chi, \mathbb{H})$, verify that it is not a theory-minimal solution and show that it belongs to NP. Indeed, it suffices to guess $\tau'$ s.t. $\tau'$ is a proper solution to $\mathbb{P}$, $\Gamma, \tau \models_{\mathcal{L}} \tau'$, and $\Gamma, \tau' \not\models_{\mathcal{L}} \tau$. Theorem 8 shows that these checks can be done in polynomial time. $\square$

**Theorem 12.** Let $\mathbb{P} = (\Gamma, p, \mathbb{H})$ be an $\mathcal{L}$-abduction problem s.t. $\Gamma$ is a set of interval clauses and $p \in \text{Pr}$. Then, for an interval term $\tau$, it is DP-complete to decide whether $\tau \in S(\mathbb{P})$.

*Proof.* Membership follows from Theorem 1. We show the hardness via a reduction from the classical solution recognition. Assume that $\mathbb{P} = (\Gamma, p, \mathbb{H})$ is a classical abduction problem with $\Gamma = \{\kappa_i | i \in \{1, \dots, n\}\}$ being a set of disjunctive clauses and that $\tau$ is a solution to $\mathbb{P}$. We define $\mathbb{P}_{\text{int}} = (\Gamma_{\text{int}}, p, \mathbb{H}_{\text{int}})$ and $\tau_{\text{int}}$ as follows:

$$ 
\begin{align} 
\Gamma_{\text{int}} &= \left\{ \bigoplus_{q_i \in \kappa_i} (q_i \ge \mathbf{1}) \oplus \bigoplus_{\neg r_i \in \kappa_i} (r_i < \mathbf{1}) \mid i \in \{1, \dots, n\} \right\} \\ 
\mathbb{H}_{\text{int}} &= \{s \ge \mathbf{1} \mid s \in \mathbb{H}\} \cup \{t < \mathbf{1} \mid \neg t \in \mathbb{H}\} \\ 
\tau_{\text{int}} &= \bigodot_{\substack{s' \in \tau \\ t' \in \tau}} (s' \ge \mathbf{1}) \odot \bigodot_{\neg t' \in \tau} (t < \mathbf{1}) 
\end{align} 
\tag{8} $$

Now let $\tau \in S(\mathbb{P})$, i.e., $\Gamma, \tau \models_{\text{CPL}}^\text{cons} p$. Clearly, $\Gamma_{\text{int}}, \tau_{\text{int}} \not\models_{\mathcal{L}} \perp$. For the entailment, assume for contradiction that $v$ witnesses $\Gamma_{\text{int}}, \tau_{\text{int}} \not\models_{\mathcal{L}} p$. Consider a classical valuation $v_{\text{cl}}$ s.t. $v_{\text{cl}}(q) = 1$ iff $v(q) = 1$. One can easily see that $v_{\text{cl}}$ witnesses $\Gamma, \tau \not\models_{\text{CPL}} p$. For the converse direction, let $\tau \in S(\mathbb{P}_{\text{int}})$. A solution for $\mathbb{P}$ can be obtained by replacing $r \ge \mathbf{1}$ with $r$ and $r < 1$ with $\neg r$. The reasoning is similar. $\square$

**Theorem 15.** Let $\mathbb{P} = (\Gamma, \tau, \mathbb{H})$ be an $\mathcal{L}$-abduction problem with $\Gamma$ a CF set of interval clauses and $\tau$ an interval term. Then it is $\mathbb{P}$-complete to check whether an interval term $\sigma$ is a (proper, minimal) solution to $\mathbb{P}$.

*Proof.* For the membership, we construct a reduction to the classical Horn abduction for which solution recognition is polynomial. Let $\Gamma = \{\kappa_1, \dots, \kappa_m, \kappa'_1, \dots, \kappa'_{m'}\}$ be a set of interval clauses of the form $\kappa_i = \bigodot_{j=1}^{n_i} (p_j \diamond c_j) \to (q_i \diamond d_i)$ and $\kappa'_i = \bigodot_{j=1}^{n'_i} (p'_j \diamond c'_j) \to \perp$.

Now, for each interval literal $\lambda$, let $r_\lambda$ be a fresh propositional variable. We define

$$ \kappa_{\mathcal{H}} := \bigwedge_{j=1}^{n_i} r_{p_j \diamond c_j} \to r_{q_i \diamond d_i}, \quad \kappa'_{\mathcal{H}} := \bigwedge_{j=1}^{n'_i} r'_{p'_j \diamond c'_j} \to \perp $$

We consider the following classical abduction problem: $\mathbb{P}_{\mathcal{H}} = (\Gamma_{\mathcal{H}}, \tau_{\mathcal{H}}, \mathbb{H}_{\mathcal{H}})$ defined as described below.

$$ 
\begin{align} 
\Gamma_{\mathcal{H}} &= \{\kappa_{\mathcal{H}} | \kappa \in \Gamma\} \cup \{\kappa'_{\mathcal{H}} | \kappa' \in \Gamma\} \nonumber \\ 
&\quad \left\{ r_{\lambda} \wedge r_{\lambda'} \to \perp \middle| \begin{array}{c} \mathcal{L} \models \lambda \odot \lambda' \to \perp \\ \text{and } \lambda' \text{ occur in } \mathbb{P}^{\odot} \end{array} \right\} \cup \nonumber \\ 
&\quad \left\{ r_{\lambda} \to r_{\lambda'} \middle| \begin{array}{c} \mathcal{L} \models \lambda \to \lambda' \\ \text{and } \lambda' \text{ occur in } \mathbb{P}^{\odot} \end{array} \right\} \nonumber \\ 
\tau_{\mathcal{H}} &= \bigwedge_{\lambda \in \tau} r_{\lambda} \nonumber \\ 
\mathbb{H}_{\mathcal{H}} &= \{r_{\lambda} | \lambda \in \mathbb{H}\} 
\end{align} 
\tag{9} $$

As one can see, $\Gamma_{\mathcal{H}}$ is polynomial in the size of $\Gamma$ and (recall Proposition 3) it takes polynomial time to determine whether $\lambda \to \lambda'$ is $\mathcal{L}$-valid and $\lambda \odot \lambda'$ is $\mathcal{L}$-unsatisfiable. Furthermore, $\Gamma_{\mathcal{H}}$ is a set of Horn formulas and only contains variables of the form $r_\lambda$ with $\lambda$ being an interval term occurring in $\mathbb{P}$. We show that $\sigma$ is a (proper) solution to $\mathbb{P}$ iff $\sigma_{\mathcal{H}} = \bigwedge_{\lambda \in \sigma} r_\lambda$ is a (proper) solution to $\mathbb{P}_{\mathcal{H}}$.

Assume that $\sigma \in S(\mathbb{P})$. We show that $\Gamma_{\mathcal{H}}, \sigma_{\mathcal{H}} \models_{\text{CPL}}^\text{cons} \tau_{\mathcal{H}}$. Let $v$ be an $\mathcal{L}$-valuation witnessing that $\Gamma, \sigma \not\models_{\mathcal{L}} \perp$. We construct the classical valuation $v_{\mathcal{H}}$ as follows:

$$ v_{\mathcal{H}}(r_{\lambda}) = \begin{cases} 1 & \text{if } v(\lambda) = 1 \\ 0 & \text{otherwise} \end{cases} 
\tag{10} $$

It is clear from the construction of $\Gamma_{\mathcal{H}}$ and $\sigma_{\mathcal{H}}$ that $v_{\mathcal{H}}$ witnesses $\Gamma_{\mathcal{H}}, \sigma_{\mathcal{H}} \not\models_{\text{CPL}} \perp$.

Now let $v$ be a classical valuation s.t. $v(\phi) = 1$ for all $\phi \in \Gamma_{\mathcal{H}}, v(\sigma_{\mathcal{H}}) = 1$ but $v(\tau_{\mathcal{H}}) = 0$. We need to define an $\mathcal{L}$-valuation $v_{\mathcal{v}}$ s.t. $v_{\mathcal{v}}(\lambda) = 1$ iff $v(r_\lambda) = 1$ would hold for every $\lambda$ occurring in $\mathbb{P}$. For every $p_j \in \text{Pr}[\mathbb{P}]$, we define

$$ 
\begin{align} 
V_{p_j} &= \bigcap [c_j, 1] \cap \bigcap (c'_j, 1] \cap \nonumber \\ 
&\quad v(r_{p_j \ge c_j}) = 1 \quad v(r_{p_j > c'_j}) = 1 \nonumber \\ 
&\quad \bigcap (c''_j, 1] \cap \bigcap [c'''_j, 1] \cap \nonumber \\ 
&\quad v(r_{p_j \le c''_j}) = 0 \quad v(r_{p_j < c'''_j}) = 0 \nonumber \\ 
&\quad \bigcap [0, d_j] \cap \bigcap [0, d'_j] \cap \nonumber \\ 
&\quad v(r_{p_j \ge d_j}) = 0 \quad v(r_{p_j > d'_j}) = 0 
\end{align} 
$$
$$ \bigcap [0, d_j''] \cap \bigcap [0, d_j''') \quad (11) \\ \mathbf{v}(r_{p_j} \le a_j'') = 1 \qquad \mathbf{v}(r_{p_j < a_j''}) = 1 $$

It is clear that $V_{p_j} \neq \emptyset$ for each $p_j$. Indeed, otherwise, there would be two variables $r_\lambda$ and $r_{\lambda'}$ s.t. $\mathbf{v}(r_\lambda) = \mathbf{v}(r_{\lambda'}) = 1$ and $\lambda$ and $\lambda'$ are two interval literals over $p_j$ with $\lambda \odot \lambda'$ being $\mathbf{k}$-unsatisfiable. Hence, $r_\lambda \wedge r_{\lambda'} \to \perp \in \Gamma_\mathcal{H}$, which means that $\mathbf{v}$ does not satisfy $\Gamma_\mathcal{H}$, contrary to the assumption.

We now set for every $p_j$, $v_\mathbf{v}(p_j) = x$ for some $x \in V_{p_j}$. It is easy to see that $v_\mathbf{v}(\theta) = 1$ for all $\theta \in \Gamma$ and $v_\mathbf{v}(\sigma) = 1$ but $v_\mathbf{v}(\tau) = 0$. Thus, $\Gamma, \sigma \not\models_k \tau$ which contradicts the assumption that $\sigma \in S(\mathbb{P})$. Thus, $\Gamma_\mathcal{H}, \sigma_\mathcal{H} \models_{CPL} \tau_\mathcal{H}$. It follows now that $\sigma_\mathcal{H}$ is a solution to $\mathbb{P}_\mathcal{H}$.

Conversely, let $\sigma_\mathcal{H}$ be a solution to $\mathbb{P}_\mathcal{H}$, that is, $\Gamma_\mathcal{H}, \sigma_\mathcal{H} \models_{CPL} \tau_\mathcal{H}$. Assume that $\mathbf{v}$ is a classical valuation witnessing $\Gamma_\mathcal{H}, \sigma_\mathcal{H} \not\models_{CPL} \perp$. We define $v_\mathbf{v}$ using (11) as in the previous part of the proof which gives us that $v_\mathbf{v}$ witnesses $\Gamma, \sigma \not\models_k \perp$. It remains to see that $\Gamma, \sigma \models_k \tau$. To do that, assume for contradiction that there is some $\mathbf{k}$-valuation witnessing $\Gamma, \sigma \not\models_k \tau$. We define $v_\mathcal{H}$ as shown in (10). It is clear that $v_\mathcal{H}$ would witness $\Gamma_\mathcal{H}, \sigma_\mathcal{H} \not\models_k \tau_\mathcal{H}$, contrary to the assumption. Hence, $\sigma \in S(\mathbb{P})$, as required.

Thus, we have that recognition of arbitrary solutions to problems whose theories are sets of cover-free clauses is polynomial. As our observation is also an interval term, it follows from Proposition 3 that verifying $\sigma \not\models_k \tau$ takes polynomial time. This means that determining whether $\sigma$ is a proper solution also takes polynomial time. Finally, to see that recognition of *entailment-minimal* solutions is polynomial as well, recall from the proof of Theorem 3 that there are only polynomially many candidate interval terms we need to check for a given $\sigma$.

For the hardness, we construct a logspace reduction of the solution recognition for classical Horn abduction problems to the solution recognition for Łukasiewicz abduction problems with cover-free theories. Namely, let $\mathbb{P} = \langle \Gamma, \tau, \mathbb{H} \rangle$ be a classical Horn abduction problem with $\Gamma$ represented as Horn implications $\eta = \bigwedge_{i=1}^m p_i \to q_i$ and $\theta = \bigwedge_{i=1}^{m'} p'_i \to \perp$ and $\mathbb{H} \cap \text{Pr}(\tau) = \emptyset$. We define

$$ \eta^{\mathcal{C}} := \bigcirc_{i=1}^{m} (p_i \geq \mathbf{1}) \to (q \geq \mathbf{1}) \qquad \theta^{\mathcal{C}} := \bigcirc_{i=1}^{m'} (p'_i \geq \mathbf{1}) \to \perp $$

and set $\mathbb{P}^{\mathcal{C}} = \langle \Gamma^{\mathcal{C}}, \tau^{\mathcal{C}}, \mathbb{H}^{\mathcal{C}} \rangle$ as follows:

$$ \begin{align} \Gamma^{\mathcal{C}} &= \{\eta^{\mathcal{C}} \mid \eta \in \Gamma\} \cup \{\theta^{\mathcal{C}} \mid \theta \in \Gamma\} \nonumber \\ \tau^{\mathcal{C}} &= \bigcirc_{q \in \tau} (q \geq \mathbf{1}) \odot \bigcirc_{\neg q \in \tau} (q \leq \mathbf{0}) \tag{12} \\ \mathbb{H} &= \{r \geq \mathbf{1} \mid r \in \mathbb{H}\} \cup \{s \leq \mathbf{0} \mid \neg s \in \mathbb{H}\} \nonumber \end{align} $$

It is clear that $\Gamma^{\mathcal{C}}$ is cover-free and that the size of $\mathbb{P}^{\mathcal{C}}$ is linear in the size of $\mathbb{P}$. Now assume that $\sigma \in S(\mathbb{P})$. We show that $\sigma^{\mathcal{C}} \in S(\mathbb{P}^{\mathcal{C}})$. First, it is clear that $\Gamma^{\mathcal{C}}, \sigma^{\mathcal{C}} \not\models_k \perp$ because $\Gamma, \sigma \not\models_{CPL} \perp$. To check the entailment, observe that there is a unit resolution inference of literals comprising $\tau$ from $\Gamma \cup \{\sigma\}$. It is clear that classical unit resolution is sound for interval clauses: if $v(p \geq \mathbf{1}) = 1$ and $v(((p \geq

$\mathbf{1}) \odot \tau) \to \lambda) = 1$, then $v(\tau \to \lambda) = 1$; if $v(p \leq \mathbf{0}) = 1$ and $v(\tau \to (p \geq \mathbf{1})) = 1$, then $v(\tau \to \perp) = 1$. Thus, reusing the classical inference in $\mathbf{k}$, we obtain $\Gamma^{\mathcal{C}}, \sigma^{\mathcal{C}} \models_k \tau^{\mathcal{C}}$, as required. Conversely, let $\sigma \in S(\mathbb{P}^{\mathcal{H}})$ and define $\sigma_{cl} = \bigwedge r \wedge \bigwedge \neg s$. It is clear that $\Gamma, \sigma_{cl} \models_{CPL} \tau$. To see that $(r \geq \mathbf{1}) \in \sigma \quad (s \leq \mathbf{0}) \in \sigma$ $\Gamma, \sigma_{cl} \not\models_{CPL} \perp$, assume for contradiction that $\Gamma, \sigma_{cl} \models_{CPL} \perp$. Then there is a unit resolution inference of the empty clause from $\Gamma \cup \{\sigma_{cl}\}$. But as we can reuse it in $\mathbf{k}$, this would mean that $\Gamma^{\mathcal{C}}, \sigma \models_k \perp$, contrary to the assumption. Contradiction.

As $\mathbb{H} \cap \text{Pr}(\tau) = \emptyset$, it follows that all solutions to $\mathbb{P}$ and $\mathbb{P}^{\mathcal{C}}$ are proper. Hence, the reduction works for both arbitrary and proper solutions. Finally, to see that recognition of entailment-minimal solutions is P-hard, one can easily check that if $\sigma \in S^{\text{min}}(\mathbb{P})$, then $\sigma^{\mathcal{C}} \in S^{\text{min}}(\mathbb{P}^{\mathcal{C}})$. Conversely, if $\sigma' \in S^{\text{min}}(\mathbb{P}^{\mathcal{C}})$, then $\sigma'_{cl} \in S^{\text{min}}(\mathbb{P})$. $\square$

**Theorem 16.** Let $\mathbb{P} = \langle \Gamma, \tau, \mathbb{H} \rangle$ be an $\mathbf{k}$-abduction problem with $\Gamma$ a CF set of interval clauses. Then it is NP-complete to decide whether $\mathbb{P}$ has (proper) solutions.

*Proof.* The membership follows from Theorem 15. For the hardness, we reuse the reduction shown in (12). $\square$