Paper deep dive

Representative Sets in Propositional Abduction

Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, Johannes K. Fichte

Year: 2026Venue: arXiv preprintArea: cs.CCType: PreprintEmbeddings: 46

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%

Last extracted: 7/24/2026, 2:44:04 AM

Summary

This paper investigates the computational complexity of the 'Representative Sets in Propositional Abduction' (REPABD) problem, which asks if a given set of explanations can represent all other explanations within a symmetric difference distance k. The authors provide a complete classical complexity classification for various constraint languages (Γ), showing that the problem is generally ΠP2-complete or coNP-hard, with only a few tractable cases. They also analyze parameterized complexity, linking the problem to the covering radius problem in coding theory, establishing new connections between non-monotonic reasoning and coding theory.

Entities (8)

REPABD · problem · 98%Propositional Abduction · concept · 95%Covering Radius Problem · problem · 92%Coding Theory · field · 90%Non-monotonic Reasoning · field · 90%Constraint Language · concept · 88%Parameterized Complexity · field · 88%Symmetric Difference · metric · 85%

Relation Signals (7)

Propositional Abduction → isa → Non-monotonic Reasoning

confidence 98% · The propositional abduction problem is a well-known form of non-monotonic reasoning

Covering Radius Problem → belongstofield → Coding Theory

confidence 95% · covering radius problem from coding theory

REPABD → isa → Propositional Abduction

confidence 95% · We consider a related representation question... We denote this problem by REPABD

REPABD → usesmetric → Symmetric Difference

confidence 92% · whether their symmetric difference is smaller than a given k

REPABD → analyzedby → Parameterized Complexity

confidence 90% · We then study the parameterized complexity for several parameters

REPABD → reducesto → Covering Radius Problem

confidence 88% · a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem

Constraint Language → determinescomplexityof → REPABD

confidence 85% · We first study this problem from a classical complexity perspective... for all possible choices of Γ

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined questions about the solution space rather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diverse solutions) in the solution space. In this paper we consider a related representation question where we ask if a given set of explanations S can represent any other explanation (that is, whether their symmetric difference is smaller than a given k). We first study this problem from a classical complexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abduction is often smaller than expected. We then study the parameterized complexity for several parameters and obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been established, but such connections seemingly become important when asking more complex questions about solution spaces.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

44,457 characters extracted from source content.

Expand or collapse full text

W. Faber, L. Giordano, R. Rocha, V. Santos Costa (Eds.): 42nd International Conference on Logic Programming (ICLP 2026) EPTCS 450, 2026, p. 1–14, doi:10.4204/EPTCS.450.1 © J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte This work is licensed under the Creative Commons Attribution License. Representative Sets in Propositional Abduction * Johannes Schmidt J ̈onk ̈oping University Mohamed Maizia J ̈onk ̈oping University Link ̈oping University Victor Lagerkvist Link ̈oping University Johannes K. Fichte Link ̈oping University The propositional abduction problem is a well-known form ofnon-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of re- sults asking more refined questions about the solution spacerather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diversesolutions) in the solution space. In this paper we consider arelatedrepresentationquestion where we ask if a given set of explanationsScan represent any other explanation (that is, whether their symmetric difference is smaller than a givenk). We first study this problem from a classical com- plexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abductionis often smaller than expected. We then study the parameterized complexity for several parametersand obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameter- ized complexity of thecovering radiusproblem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been es- tablished, but such connections seemingly become important when asking more complex questions about solution spaces. Keywords:Propositional Abduction, Computational Complexity, Post’s Framework, Fine-grained Reasoning 1 Introduction Thepropositional abductionproblem is a well-known form of non-monotonic reasoning with many applications in e.g, AI and knowledge representation [10, 9, 23, 31, 22]. Here, we are asked to explain a givenmanifestation. The explanation thus needs to logically entail the manifestation, and, to avoid trivial explanations, be consistent with the given knowledge base.For example, consider a medical diagnosis setting where a patient may develop a certain symptom depending on underlying conditions. We could then have propositional variablesa(the patient has a weakened immune system),b(the patient has a bacterial infection),c(the patient has a viral infection),d(the patient is exposed to severe environmental stress), andm(the patient develops a high fever). The knowledge base could then encode the following medical rules: • If the patient has a weakened immune system and a bacterial infection, then they develop a high fever. • If the patient has a weakened immune system and a viral infection, then they develop a high fever. • If the patient has a weakened immune system and is exposed tosevere environmental stress, then they develop a high fever. • The patient cannot simultaneously have a bacterial and a viral infection. * Author names are stated in reverse alphabetical order. 2Representative Sets in Propositional Abduction Formally, we could represent this as KB=a∧b→m,a∧c→m,a∧d→m,¬(b∧c). The manifestation is the observation that the patient has developed a high fever, i.e.,M=m, and the set of hypotheses isH=a,b,c,d. Then, for example,a,b(weakened immune system and bacterial infection) anda,b,d(additionally, stress) are both possible explanations, but, unless there is further evidence, one may argue thata,bis preferable toa,b,dsince it makes fewer assumptions. In this scenario, it seems desirable to considerallminimal explanations, revealing that the fever can be explained by a weakened immune system combined with exactly one of the mutually exclusive infections, or with environmental stress. As might be expected, computing/counting all (minimal) explanations is computationally expen- sive [21, 7], and even deciding existence of just a single explanation isΣ P 2 -complete [13]. Nevertheless, there has been many attempts to reason about the set of solutions, e.g. by identifyingfacets[1, 15, 28], and findingdiversesolutions (induced by a given distance metric between solutions). For example, diverse solutions have been considered foranswer set programming[12], abduction [30],constraint satisfaction problems[20], satisfiability problems [26], and a wealth of graph problems [2, 16, 17]. Inspired by the success of this approach and recent work on answer set programming [3] we in this paper consider a related question: does there exist a set of explanations thatrepresentall (minimal) explanations? We formulate this as a decision problem and then qualify our problem with a parameter k≥0, a set of explanationsS, and want to know if every explanation is within distancekfrom at least one explanation inS. In this caseSis called(k-)representative. Thus, unlesskis large, we expect the set Sto correlate with diverse solutions. We denote this problem by REPABD, and the corresponding problem for representing subsetmini- mal explanations, by REPABD ⊆ . If no assumptions are imposed on the knowledge base KB it is easy to show that both these problems areΠ P 2 -complete, and we therefore attempt a more fine-grained picture of the complexity with restricted knowledge bases (e.g., whether it is in Horn, or in 2-CNF). We write REPABD(Γ)(REPABD ⊆ (Γ)) for this problem whereΓis a set of relations, and then require that the knowledge base is given by a conjunctiveΓ-formula, i.e., each atom is of the formR(x 1 ,...,x k )forR∈Γ and variablesx 1 ,...,x k . We formally introduce this problem in Section 3 together with a few useful definability notions. Then, for our main technical contributions, we (in Section 4) classify the classical complexity of REPABD(Γ)and REPABD ⊆ (Γ)for all possible choices ofΓ. Our classification reveals that the two problems have few tractable cases. For example, ifΓcan express the “trivial” unary relationt=(0),(1)then REPABD(Γ)is at least coNP-hard. Surprisingly, REPABD ⊆ (Γ)fares marginally better in comparison and we prove that it isin P if each relation isstrictly essentially positive, or the dual case of beingstrictly essentially negative. However, it should be noted that tractability in this case stems from rather trivial reasons, and to extend the tractable fragments we (in Section 5) turn toparameterized complexity. Here, we relax polynomial time to additionally allow a factorf(p)wherep∈Nis a parameter (e.g.,|H|,|M|,k, or a graph parameter of KB) andf:N→Na computable function. A problem admitting such a running time is said to befixed-parameter tractable (FPT). The parameterized complexity of abduction is well understood for many natural parameters [24, 14] and admits non-trivial FPT cases, so there is reason for acertain optimism. We consider many different parameters (k,|H|,|M|, and|S|) and establish FPT for|H|ifΓisSchaeferand for|S|ifΓis strictly essentially positive. Importantly, we complement this with many lower bounds that rule out FPT under widely believed conjectures in parameterized complexity. Interestingly, by considering such “fine-grained” questions about the set of explanations, we are able to make connections to problems previously unconnected to non-monotonic reasoning. For example, one of our main sources of hardness stems from thecovering radiusproblem [18], and one of our main FPT results are based on a reduction to theclosest string problem[19]. As we show, a complete parameter- J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte3 ized complexity classification of REPABD(Γ)would simultaneously need to resolve the parameterized complexity of the covering radius problem (with parameterr). We discuss this and other questions in Section 6. Due to space constraints the proof of statements marked with⋆have been omitted. 2 Preliminaries We follow standard notions in computational complexity theory [11], and propositional logic. Below, we briefly state the most important notions. 2.1 Computational Complexity LetΣandΣ ′ be finite alphabets. Aninstanceis a stringI∈Σ ∗ and||I||denotes its size. Adecision problemis a languageL⊆Σ ∗ . Recall that P and NP are the classes of deterministically and non- deterministically polynomial-time solvable decision problems [5]. A polynomial-time many-to-one re- duction (≤ P m ) fromLtoL ′ is a functionr:Σ ∗ →Σ ′ ∗ such thatI∈Lif and only ifr(I)∈L ′ andris computable in timeO(||I|| c )for some constantc. We also use the Polynomial Hierarchy (PH) where ∆ P 0 : =Π P 0 : =Σ P 0 : =P,∆ P i+1 : =P Σ P i ,Σ P i+1 : =NP Σ P i , andΠ P i+1 : =coNP Σ P i fori>0. For a decision problem X, we write Xfor its complement. Aparameterized problemis a setL⊆Σ ∗ ×N. It isfixed-parameter tractable(FPT) if membership of(I,k)can be decided in timef(k)· ||I|| c for a computable functionfand a constantc. Afixed- parameter (FPT) reductionfromLtoL ′ is a mappingP(with respect to computablef,p:N→Nand a constantc) where we for any(I,k)∈Σ ∗ ×N) have (1)(I,k)∈Lif and only ifP(I,k) = (I ′ ,k ′ )∈L ′ , (2) k ′ ≤p(k), and (3)P(I,k)can be computed inf(k)· ||I|| c time. A problem is W[1]-hardif it admits an FPT-reduction from INDEPENDENTSET. Another important W[1]-hard problem isweighted SATwhere we ask if a given propositional formula φhas a model of weight≥k. We let WSAT(2−CNF − )denote its restriction to negative 2-CNF. Finally, for a classical complexity classC, we define para-Cas the class of all parameterized problems reducible to a language inCvia a computable parameter transformation, allowing us to speak of classes such as para-NP, para-coNP, para-DP, and para-coDP. Propositional Logic.Aliteralis a variablexor its negation¬x. Aclauseis a disjunction of literals, often represented as a set. A clause of arity 1, i.e., either(x)or(¬x), is aunit clause. We work in a general setting where atoms can be expressions of the formR(x 1 ,...,x r )for variablesx 1 ,...,x r and an r-ary relationR⊆ 0,1 r . A functionf:x 1 ,...,x r → 0,1is then said to satisfy an atomR(x 1 ,...,x r ) if(f(x 1 ),...,f(x r ))∈R. A (conjunctive)propositional formula φis a conjunction of atoms and we write var( φ)for its set of variables. A mappingσ: var(φ)7→ 0,1is called anassignmentto the variables of φand amodelof a formulaφis an assignment to var(φ)that satisfiesφ. For two formulasψandφ, we write ψ|=φif every model ofψalso satisfiesφ. 2.2 Restrictions of Constraint Languages We work in a generalized setting where atoms can be formed by combining relations and variables. Then, aconstraint languageΓis a set of Boolean relations, and aΓ-formulaover some variablesVis a propositional formula φwhereR∈Γandx 1 ,...,x r ∈Vfor each atom in the formulaR(x 1 ,...,x r ). For a constraint languageΓ, we write SAT(Γ)for the problem of deciding if a givenΓ-formula admits at least 4Representative Sets in Propositional Abduction co-clone clauses/equationname/indication BR(I 2 )all clausesall Boolean relations I 0 at least one negative literal per clause0-valid IN 2 NAE =0,1 3 \ 000,111complementive INDUP =0,1 3 \ 101,010complementive and 1- and 0-valid IE 2 clauses with at most one positive literalHorn IV 2 clauses with at most one negative literaldualHorn IL 2 all affine clauses (all linear equations)affine IL(x 1 ⊕ · ⊕x n =0),nevenaffine and 1- and 0-valid ID 2 clauses of size 1 or 2Krom, bijunctive, 2-CNF IDaffine clauses of size 2strict 2-affine IM(x 1 →x 2 )implicative and 1- and 0-valid IS 12 (x 1 ),(¬x 1 ∨ · ∨ ¬x n ),n≥0,(x 1 =x 2 )essentially negative (EN) IS k 11 (x 1 →x 2 ),(¬x 1 ∨ · ∨ ¬x n ),k≥n≥0- IS k 1 (¬x 1 ∨ · ∨ ¬x n ),k≥n≥0,(x 1 =x 2 )negative (N) of widthk IS 02 (¬x 1 ),(x 1 ∨ · ∨x n ),n≥0,(x 1 =x 2 )essentially positive (EP) IR 1 (x 1 ),(x 1 =x 2 )- IR 0 (¬x 1 ),(x 1 =x 2 )- IR(IBF)(x 1 =x 2 )- Table 1: Overview of some co-clones and clause descriptions[27]. one model. Usually, we do not distinguish between the relation or a clause defining the relation. For example, we simply write(x)for the unary relation(1),(¬x)for(0),(x 1 →x 2 )or(¬x 1 ∨x 2 )for (0,0),(0,1),(1,1), and so on. The empty set /0 is the (nullary) relation that is always false, we write R = for the equality relation(0,0),(1,1)(but often written in infix form as(x=y)instead ofR = (x,y)), andtfor the trivial unary relation(0),(1)that is always true. For a constraint languageΓandk≥1, we often use the notationk-Γfor the set of relations/clauses of arity at mostk(e.g., 2-CNFcontains all clauses of arity 1 and 2). Additionally, for a languageΓwe, let (1)Γ − =Γ\ (x),(¬x)beΓwithout the two unit clauses, and (2)Γ + =Γ∪ (x),(¬x)beΓexpanded with the two unit clauses. A languageΓisb-validforb∈ 0,1, if(b,...,b)∈Rfor eachR∈Γ. We introduce the most important constraint languages for the purpose of this paper in Table 1. We also write EP − for the set ofstrictly essentially positive clausesEP\ (x=y)and EN − =EN\ (x=y)for the set ofstrictly essentially negative clauses. To avoid doing an exhaustive case analysis ofallpossible constraint languages we introduce a useful closure property on relations. Say that anr-ary relationRhas aprimitive positive definition(p-definition) overΓif R(x 1 ,...,x r ):=∃y 1 ,...,y n . φ(x 1 ,...,x r ,y 1 ,...,y n ) where φis a(Γ∪ /0,t,(x=y))-formula. Thus, put otherwise,Rcan be defined as the set of models of ∃y 1 ,...,y n . φ(x 1 ,...,x r ,y 1 ,...,y n )with respect to the free variablesx 1 ,...,x r . Definition 2.1.For a constraint languageΓwe lethΓibe the smallest set of relations containingΓand where R∈Γfor any p-definable relation R overΓ. The setΓis in this context said to be abase, andhΓiis sometimes called arelational clone, or a co-clone. For details, we refer to the work by [4]. We note that the complexity of SAT(Γ)is completely J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte5 determined due to Schaefer’s famous dichotomy result: it ispolynomial ifΓis 0- or 1-valid orSchaefer (that is,Γis Horn, or dualHorn, or affine, or 2-CNF) and NP-complete otherwise [29]. 2.3 Propositional Abduction LetΓbe a constraint language, for example, a set of clauses. An instanceIof thepositive propositional abduction problem overΓ, ABD(Γ)for short, is a tupleI= (KB,H,M)with KB being aΓ-formula over a finite set of Boolean variables called theknowledge base(ortheory),H⊆var(KB)calledhypotheses, M⊆var(KB)calledmanifestations. Since we have defined aΓ-formula as a conjunctive formula with atoms fromΓwe sometimes take the liberty of viewing the knowledge base as a set rather than as a formula. Apositive explanation E,explanationfor short, is a subsetE⊆Hsuch that (i) KB∧Eis satisfiable and (i) KB∧E|=M. An explanationEis(subset-)minimalif no other setE ′ (Eis an explanation ofI. The problem ABD(Γ)asks whether there is an explanation, which in the decision context is the same as asking whether there is a minimal explanation. IfΓis arbitrary, we omitΓfrom the problem and write ABD. Note that the complexity of ABD(Γ)is completely determined [27]. We writeE(I)to refer to the set of all explanations andE M (I)for the set of all subset-minimal explanations. Example 2.2.Consider the abduction example from Section 1 where I= (KB,H,M)with KB=a∧b→ m,a∧c→m,a∧d→m,¬(b∧c), manifestation m, and the hypothesesa,b,c,d. ThenE M (I) = a,b,a,c,a,dandE(I) =a,b,a,c,a,d,a,b,d,a,c,d. 3 The Representative Explanation Problem We begin the technical part of the paper by formally introducing our problem as well as the simplifying algebraic machinery. LetI= (KB,H,M)be an ABD instance. For a setE⊆H, defineS k (E) =E 1 ∈ E(I)|d(E,E 1 )≤kwhered(·,·)denotes the symmetric difference, i.e.,d(E 1 ,E 2 ) =|E 1 △E 2 |=|(E 1 ∪ E 2 )\(E 1 ∩E 2 )|=|x∈H|x∈E 1 andx/∈E 2 orx/∈E 1 andx∈E 2 |, i.e.,S k (E)is the set of explanations within Hamming distancekofE. For a fixedk, an explanationE∈E(I)is calledk-representative, if |S k (E)|is maximal. That is, such anErepresents maximally many explanations. We extend this notion to sets of explanations as follows: for a fixedk, a set of explanationsS⊆E(I)is calledk-representative, ifE(I) = ⋃ E∈S S k (E). We then consider the following problem where the task is to verify if a set of explanations isk- representative or not. REPABD(Γ) Given:An ABD(Γ)instanceI= (KB,H,M), a setS⊆E(I), andk≥1. Task:IsS k-representative forI? We also consider REPABD(Γ)restricted to⊆-minimal explanations (given nowS⊆E M (I)check if E M (I) = ⋃ E∈S S M k (E), whereS M k (E) =E 1 ∈E M (I)|d(E,E 1 )≤k) and write REPABD ⊆ (Γ)for this variant. Example 3.1.We continue with Example 2.2 where we had KB=a∧b→m,a∧c→m,a∧d→ m,¬(b∧c), M=m, H=a,b,c,d, andE(I) =a,b,a,c,a,d,a,b,d,a,c,d. Then S 1 =a,bis not 2-representative, since d(a,b,a,c,d) =3. But S 2 =a,dis 2-representative, since d(a,d,E)≤2for all E∈E(I), as is easily verified. 6Representative Sets in Propositional Abduction Before turning to the complexity of REPABD(Γ)and REPABD ⊆ (Γ)we show how to apply the algebraic approach — with a minor modification. First, we saythat a p-definitionR(x 1 ,...,x r ):= ∃y 1 ,...,y n . φ(x 1 ,...,x r ,y 1 ,...,y n )isequality-free(efpp) if each atom inφis fromΓ∪ /0, i.e., we do not allow (1) the equality relation, or (2) the full relationt. We lethΓi 6= be the smallest set of relations containingΓclosed under such definitions. We have the following basic characterization (where a relationRis said to be constant if|R|=1). Before stating and proving the lemma we need a few additionalpreliminaries. For a tuplet= (x 1 ,...,x i ,...,x n )∈ 0,1 n andi∈[n] =1,...,nwe writet[i] =x i for theith component. ForR⊆ 0,1 n of aritynwe say thati∈[n]isfictitiousif(x 1 ,...,x i−1 ,x i ,x i+1 ,...,x n )∈Rif and only if we have (x 1 ,...,x i−1 , ̄x i ,x i+1 ,...,x n )∈R, and it isredundantif there existsj∈[n],j6=i, such thatt[i] =t[j]for anyt∈R. Furthermore, say thatRisirredundantif it has no redundant coordinates, and that it isprime if it is irredundant and has no fictive coordinates. We can nowrelate these notions to efpp-definability as follows. Lemma 3.2.(⋆) LetΓbe a set of Boolean relations and let R∈ hΓi. If 1. R is prime then R∈ hΓi 6= , 2. R is irredundant then R∈ hΓ∪ ti 6= , and 3. otherwise R∈ hΓ∪ R = i 6= . This in turn leads to the following classification of efpp-closed sets. Lemma 3.3.LetΓbe a set of Boolean relations. If 1. if R = ∈ hΓi 6= thent∈ hΓi 6= , 2. if R = ∈ hΓi 6= thenhΓi 6= =hΓi, 3. ifΓcontains a non-constant relation thenhΓi 6= =hΓ∪ ti 6= , and 4. ift/∈ hΓi 6= thenhΓi 6= (hΓ∪ ti 6= (hΓ∪ R = i 6= =hΓi, andh∆i 6= ∈ hΓi 6= ,hΓ∪ti 6= ,hΓ∪ R = i 6= for any∆such thathΓi=h∆i. Proof.The first claim follows immediately since we can definet(x)via the definition(x=x). For the second claim: if we can efpp-defineR = then we (by the first claim) can also efpp-definet, and any p- definition (possibly usingR = - ort-constraints) can be converted into a suitable efpp-definition. For the third claim, letR∈Γbe a non-constant relation, of arity, sayr, and let 1≤i≤rbe an argument such that |x i |(x 1 ,...,x i ,...,x r )∈R|=2. Thent(x):=∃x 1 ,...,x i−1 ,x i+1 ,...,x r .R(x 1 ,...,x i 1 ,x,x i+1 ,...,x r ). For the fourth and last claim,hΓi 6= (hΓ∪ ti 6= follows from the assumption thatt/∈ hΓi 6= . For the second inclusionhΓ∪ ti 6= (hΓ∪ R = i 6= , observe thatR = has no fictitious argument, and, hence, ifR = ∈ hΓ∪ ti 6= thenR = ∈ hΓi 6= (by Lemma 3.2). But then (as established in the first item of this lemma)hΓi 6= =hΓiwhich contradicts the assumption thatt/∈ hΓi. Hence,R = /∈ hΓ∪ ti 6= and the inclusionhΓ∪ ti 6= (hΓ∪ R = i 6= must be proper. Now, consider a∆such thath∆i=hΓi. The claim thath∆i 6= ∈ hΓi 6= ,hΓ∪ti 6= ,hΓ∪ R = i 6= then follows through a similar case analysis: if every relation is prime, thenh∆i 6= =hΓi 6= , if every relation is irredundant thenh∆i 6= ∈ hΓi 6= ,hΓ∪ ti 6= , and if these two cases do not apply thenh∆i 6= =hΓi. We remark that disallowing equality is a fairly standard assumption for certain problems [6, 24, 25, 8] buttis normally such a harmless relation that it is not explicitly acknowledged in definitions. However, we will later see that their presencedomake a difference for the REPABD(Γ)problem in the sense that there are languagesΓsuch that REPABD(Γ)is in P but REPABD(Γ∪ t)is intractable. With this in mind we obtain the following basic reducibility result. J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte7 Lemma 3.4.(⋆) LetΓandΓ ′ be two constraint languages. IfΓ ′ ⊆ hΓi 6= , thenREPABD(Γ ′ )≤ P m REPABD(Γ)andREPABD ⊆ (Γ ′ )≤ P m REPABD ⊆ (Γ). We further need the following expressiveness result. Lemma 3.5.(⋆) LetΓbe a constraint language. IfΓ6⊆ 〈 EP − 〉 6= andΓ6⊆ 〈 EN − 〉 6= then(x=y)∈ hΓi 6= andhΓi=hΓi 6= . 4 Classical Complexity We begin by analyzing the “classical” complexity of REPABD(Γ), i.e., whether it is in P, or in an in- tractable class, and thus study the complexity of the problem up to polynomial-time reductions. We first observe a straightforward upper bound. Lemma 4.1.REPABD(Γ)is inΠ P 2 . Proof.The following non-deterministic algorithm shows that REPABD(Γ)(recall that this is the com- plement of REPABD(Γ)) is inΣ P 2 . We are given an instance(KB,H,M), a setS⊆E(I), andk≥1. We then guess anE ′ ⊆H, and verify that (1)E ′ ∈E(I)— feasible with an NP- and a coNP-oracle (first check if KB∧E ′ is satisfiable, and then if KB∧E ′ |=M) (2)E ′ /∈ ⋃ E∈S S k (E)— feasible with a coNP-oracle (since the complement question is in NP: guess an E∈Sand verify thatd(E,E ′ )≤k). Recall that for a languageΓwe letΓ + beΓexpanded with the two constant Boolean relations. We have the following useful conditional upper bound. Lemma 4.2.(⋆) IfSAT(Γ + )∈PthenREPABD(Γ)∈coNP, for any constraint languageΓ. The following lemma lets us inherit numerous hardness results from ABD. Lemma 4.3.(⋆) LetΓbe a constraint language. Then ABD(Γ)≤ P m REPABD(Γ). However, the following lemma proves that REPABD is generally harder than ABD since it estab- lishes coNP-hardness for many fragments where ABD is tractable. Recall thatt=(0),(1)and that T=(1). In the reduction we use the NP-completecovering radius problem[18], where an instance is given by a binary codeC⊆ 0,1 n and an integerr, and the question is whether there is a vector v∈ 0,1 n that has Hamming distance greater thanrfrom every element inC(thus thecovering radius ofCis greater thanr). Lemma 4.4.REPABD(Γ)is coNP-hard for anyΓsuch thatt∈ hΓi 6= or T∈ hΓi 6= . Sketch.We reduce from the covering radius problem. Intuitively, weencode an instance(C,r)of this problem by introducing a fresh variable for each coordinateof the codewords and constructing KB so that all subsets of these variables form candidate explanations. The setSis defined to correspond precisely to the codewords inC, and the distance parameterkis set tor. Under this construction, any explana- tion that isnot k-represented byScorresponds exactly to a vector at Hamming distance greaterthanr from all codewords inC. Conversely, if every vector lies within distancerof some codeword, then all explanations arek-represented, yielding a positive instance. We obtain the following complexity classification of REPABD(Γ). Theorem 4.5.LetΓbe a constraint language. ThenREPABD(Γ)is 8Representative Sets in Propositional Abduction 1.Π P 2 -complete ifIN 2 ⊆ hΓi ⊆I 2 orII 0 ⊆ hΓi ⊆I 2 , 2.coNP-hard andNP-hard ifIN⊆ hΓi, 3.coNP-complete if C⊆ hΓi ⊆D for C∈ IS 2 1 ,IM,IR 1 ,ID,ILand D∈ IE 2 ,IL 2 ,IV 2 ,ID 2 , 4.coNP-complete ifIBF⊆ hΓi ⊆IR 0 andt∈ hΓi 6= , and 5.∈Potherwise. Proof.First, assume thatIN 2 ⊆ hΓi ⊆I 2 or thatII 0 ⊆ hΓi ⊆I 2 . From Lemma 4.1 we know that REPABD(Γ)∈Π P 2 , and ABD(Γ)isΣ P 2 -complete in this case, which in combination with Lemma 4.3 gives the desiredΠ P 2 -hardness. Second, assume thatIN⊆ hΓi. Then ABD(Γ)is coNP-hard, and Lemma 4.3 therefore gives NP-hardness for REPABD(Γ). For the coNP-hardness claim we first ob- serve thatΓmust contain a non-constant relation, which from Lemma 3.3 implies thatt∈ hΓi 6= , and we finally get coNP-hardness from Lemma 4.4. Third, assume thatC⊆ hΓi ⊆DforC∈ IS 2 1 ,IM,IR 1 ,ID,IL andD∈ IE 2 ,IL 2 ,IV 2 ,ID 2 . Then SAT(Γ + )∈P [29] and we therefore (via Lemma 4.2) conclude that REPABD(Γ)is in coNP. For hardness, first assume thathΓi 6=IR 1 . Then we similarly to the above case observe thatΓmust contain a non-constant relation, and we apply Lemma 4.4for the desired re- sult. ForhΓi=IR 1 we observe that any p-definition ofT(possibly usingR = andt) can be simplified into an equivalent p-definition still definingT, and we then apply Lemma 4.4. Fourth, the case when IBF⊆ hΓi ⊆IR 0 andt∈ hΓi 6= also follows from Lemma 4.4. It can be verified that the only remaining case is whent/∈ hΓi 6= and ifhΓi=IBForhΓi=IR 0 . We assume thathΓi=IR 0 since it subsumes the other case. We now apply Lemma 3.3 and conclude thathΓi 6= =h/0,Fi 6= . In this case REPABD(Γ)can be solved in polynomial time. For an instance (KB,H,M,S,k)we first check if KB=/0. If so,H=M=/0, and the only possible explanation isE=/0, and we answer yes ifS=/0and no ifS=/0. If, on the other hand, KB6=/0 then we first check if there exists a constraint /0(x)in KB. If so, thenE((KB,H,M)) =/0 since KB is not satisfiable, and we can answer yes or no via a simple case analysis. Otherwise, we must haveF(x)for each atom in KB, but then we either have no explanation, orE=/0=Mas the only possible explanation, and we can easily answer yes or no. We continue by considering the subset-minimal variant REPABD ⊆ of REPABD, which, surprisingly, turns out to be easier for certain fragments. We obtain tractability for essentially negative and essentially positive fragments, as long as the equality constraint cannot be expressed. Recall that EP − and EN − denote the sets of strictly essentially positive, respectively negative, clauses. Lemma 4.6.REPABD ⊆ (Γ)∈PifΓ⊆ 〈 EP − 〉 6= orΓ⊆ 〈 EN − 〉 6= . Proof.Let(KB,H,M,S,k)be an instance of REPABD ⊆ (Γ). We assume that eachR∈Γis represented by a conjunctive formula over EP − (or EN − ). We can then without loss of generality assume that each atom in KB is from EP − (respectively, from EN − ). In EN − , variables inMcan either appear as positive singletons, or as negative literals in a negative clause. If the abduction problem has an explanation, then there exists a unique subset-minimal explana- tionE=M∩H \ m|(m)∈KB. This is because everym∈Mis either inHand entails itself, orm is already true by being a positive singleton, or there is no solution. Similarly, in EP − , anym∈Mis either a singleton that is already always true, orm∈Hentails itself, or the problem has no solution. Again, there can onlybe a single subset-minimal explanation E=M∩H \ m|(m)∈KB. J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte9 It suffices to check if∀c i ∈S:d(E,c i )>k, which can be done in linear time. This concludes the proof. If equality can be expressed, however, we obtain coNP-hardness. Lemma 4.7.(⋆)REPABD ⊆ (Γ)is coNP-hard for any languageΓsuch that R = ∈ hΓi 6= . Furthermore, we also obtain all hardness results from ABD again, analogously to Lemma 4.3. Lemma 4.8.(⋆) LetΓbe a constraint language. ThenABD(Γ)≤ P m REPABD ⊆ (Γ). The following Theorem summarizes the results on REPABD ⊆ . Theorem 4.9.(⋆) LetΓbe a constraint language. ThenREPABD ⊆ (Γ)is 1.Π P 2 -complete ifIN 2 ⊆ hΓi ⊆I 2 orII 0 ⊆ hΓi ⊆I 2 . 2.coNP-hard andNP-hard ifIN⊆ hΓi. 3.coNP-complete if C⊆ hΓi ⊆D for C∈ IM,ID,ILand D∈ IE 2 ,IL 2 ,IV 2 ,ID 2 . 4.coNP-complete ifIBF⊆ hΓi ⊆D for D∈ IS 12 ,IS 02 , andΓ6⊆ 〈 EP − 〉 6= andΓ6⊆ 〈 EN − 〉 6= . 5.∈Potherwise (Γ⊆ 〈 EP − 〉 6= orΓ⊆ 〈 EN − 〉 6= ). 5 Parameterized complexity Having exhausted all possible sources of polynomial-time solvability we now turn our attention to pa- rameterized complexity. We writeP-REPABD(Γ,ℓ)whereℓis the type of parameter in question. We consider several different parameters beginning withkitself (i.e., thekin the given REPABD(Γ)in- stance), and then continuing with|H|,|M|, and|S|. 5.1 Parameterk Given a REPABD(Γ)instance(KB,H,M,S,k)we first consider thekitself as parameter. While this may feel like an obvious parameter choice we will soon prove thatthe parameter is not likely to help much (coW[1]-hard) for most choices ofΓ. Lemma 5.1.P-REPABD(Γ,k)is coW[1]-hard for anyΓsuch thatIS 2 1 ⊆ hΓi. Proof.We begin by giving a reduction from the W[1]-complete problem WSAT(2−CNF − )to the com- plement ofP-REPABD(∆,k), where∆=(¬x 1 ∨ ¬x 2 )contains a single negative 2-clause. In the end, we show why this also gives coW[1]-hardness forP-REPABD(Γ,k). Hence, let( φ,k)be an instance of WSAT(2−CNF − ), that is,φis a negative 2-CNFformula over nvariables,x 1 ,...,x n , and the question is whether there is a model of weight≥k. We map( φ,k)to the instance(KB,H,M,S,k ′ )ofP-REPABD(∆,k), where KB= φ,H=x 1 ,...,x n ,M=/0,S=/0, k ′ =k+1. Note that KB only uses the constraint(¬x∨ ¬y)∈IS 2 1 . To prove correctness we use the following observation. ⋃ E∈S S k ′ (E) =S k ′ (/0) =all explanations of weight≤k ′ <k(1) In other words,Srepresents precisely all explanations of weight less thank. Assume( φ,k)is a positive instance of WSAT(2−CNF − ). That is, there is a modelσofφof weight at leastk. We defineE=x∈H| σ(x) =1and note that|E| ≥k. By construction, KB∧Eis consistent 10Representative Sets in Propositional Abduction and entailsM=/0. Therefore,Eis an explanation. Since|E| ≥k,Eis not represented byS(confer observation 1). Therefore,(KB,H,M,S,k ′ )is a negative instance. Conversely, assume(KB,H,M,S,k ′ )is a negative instance. That is, there is an explanationEthat is not represented. By observation 1 we conclude that|E| ≥k. SinceEis an explanation, KB∧Emust be consistent. We conclude that φmust admit a model of weight≥k, thus(φ,k)is a positive instance of WSAT(2−CNF − ). Last, we observe that∆contains a single prime relation (no fictitious or redundantarguments). Hence, if∆⊆ hΓithen∆⊆ hΓi 6= (Lemma 3.2), and we then apply the reduction in Lemma 3.4 together with the observation that this reduction does not affect the parameterkat all. We prove an analogous bound for any languageΓthat can express implication. Lemma 5.2.(⋆)P-REPABD(Γ,k)is coW[1]-hard for anyΓsuch thatIM⊆ hΓi. The three main classes that we are missing for a complete classification are linear equations (Γ⊆IL 2 ), complementive languages (Γ⊆IN 2 ), and any language belowIS 02 (essentially positive). We do not fully manage to describe these cases but can for the latter at leastprove that its parameterized complexity essentially coincides with the parameterized complexity of the covering radius problem (with parameter r). We prove a slightly stronger result and prove that we only need to consider strictly essentially positive clauses, i.e., we do not need the equality relation in the reduction. Lemma 5.3.(⋆) The covering radius problem (with parameter r) is FPT-equivalent with the complement ofP-REPABD(EP − ,k). 5.2 Parameter|H| Next, we consider the size of the hypothesis,|H|, as parameter, where we obtain a straightforward parameterized dichotomy. The FPT case can be proven as follows. Lemma 5.4.P-REPABD(Γ,|H|)∈FPTifΓis Schaefer. Proof.We can loop over all explanation candidatesE⊆Hin brute force time 2 |H| . Since the parameter is|H|, this is FPT-time. Now we only need to check for each such candidateE1) whether it is an explanation, and 2) if so, whether it isk-represented bySor not. Step 1) amounts to checking whether KB∧Eis satisfiable and whether KB∧E|=M. Both checks can be achieved in polynomial time since for Schaefer languages SAT(Γ + )∈P. Step 2) amounts to looping over the elements ofSand computing for eachE ′ ∈Swhetherd(E,E ′ )≤kor not. This can be done in polynomial time, sinceSis part of the input. Using two hardness results from [24] this leads to the following dichotomy (see the full version for details). Theorem 5.5.LetΓbe a constraint language. ThenP-REPABD(Γ,|H|)is 1.para-coDP-hard ifIN 2 ⊆ hΓiorII 0 ⊆ hΓi. 2.para-NP-hard ifIN⊆ hΓi. 3.∈FPTotherwise (that is,Γ⊆D for D∈ IE 2 ,IL 2 ,IV 2 ,ID 2 ). J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte11 5.3 Parameter|M| For the size of the manifestation (|M|) we currently lack FPT cases, but, on the other hand, can show para-coNP-hardness for the majority of constraint languages. Lemma 5.6.P-REPABD(Γ,|M|)is para-coNP-hard for anyΓsuch thatt∈ hΓi 6= or T∈ hΓi 6= . Proof.The construction is the same as in Lemma 4.4. We note that in that construction|M|is constant. 5.4 Parameter|S| The last parameter that we consider is the number of sets|S|. We first observe a hard case by using Lemma 4.3. Lemma 5.7.(⋆)P-REPABD(Γ,|S|)is para-coNP-hard for anyΓsuch thatIS 2 11 ⊆ hΓi. 2 + i lly iti n IBF IR 1 IR 0 IR 2 IM IM 1 IM 0 IM 2 IS 2 1 IS 3 1 IS 1 IS 2 12 IS 3 12 IS 12 IS 2 11 IS 3 11 IS 11 IS 2 10 IS 3 10 IS 10 IS 2 0 IS 3 0 IS 0 IS 2 02 IS 3 02 IS 02 IS 2 01 IS 3 01 IS 01 IS 2 00 IS 3 00 IS 00 ID ID 1 ID 2 IE IE 1 IE 0 IE 2 IV IV 0 IV 1 IV 2 IL IL 0 IL 1 IL 3 IL 2 IN IN 2 I I 0 I 1 I 2 Complexity of p-Rep-ABD(||): para- 2 -hard para-NP-hard para-coNP-hard FPT if = unknown Figure 1: The complexity ofP-REPABD(Γ,|S|)illustrated via Post’s lattice. Lemma 5.8.P-REPABD(EP − ,|S|)is in FPT. Proof.We first observe thatP-REPABD(EP − ,|S|)is FPT-equivalent to the covering radius problem by the same reduction used in Lemma 5.3. Next, we show FPT for this problem by giving an FPT-reductionto theclosest string problemwith alphabetΣ=0,1. Here, we are given a set of stringsC, a radiusrand want to know if there exists x∈ 0,1 n such thatd(x,c i )≤rfor everyc i ∈C. This problem is known to be FPT with respect to |C|[19]. Given an instanceC⊆ 0,1 n andr≥1 of the covering radius problem we map it to an instance(C ′ ,r ′ )of the closest string problem as follows. •C ′ = c i |c i ∈Cwherec i is the bit-wise complement ofc i , 12Representative Sets in Propositional Abduction •r ′ =n−r. The correctness is as follows: assume∃x∈ 0,1 ∗ :∀c i ∈C:d(x,c i )>r↔ |x∩c i |>r↔ |x∩c i | ≤ n−r. Moreover, the reduction can clearly be carried out in FPT time (indeed, even polynomial time) and preserves the parameter since|C ′ |=|C|. This concludes the proof. This result extends toP-REPABD(Γ,|S|)for anyΓ⊆ 〈 EP − 〉 6= since the reduction in Lemma 3.4 does not affect the parameter|S|. 6 Conclusion We introduced representative sets in propositional abduction and illustrated how it gives a better under- standing of the space of possible explanations; for example, (recall Section 1), in a medical situation, representative abduction can tell doctors if their set of hypothesis has covered all major possibilities to explain the symptoms or if they might have missed something crucial. Complexity-wise, we have es- tablished an almost complete classification of the problem for constraint language restrictions (Post’s lattice). Although the problem admits almost no tractable cases in its normal form, the subset minimal variant and the parametrized complexity approach give us several additional tractable cases. Let us now discuss some potential future research directions. Completing the classification.We have three open cases shared by representative abductionand its subset minimal variant. These are the 1-valid languages. Wehave already established that they are both NP- and coNP-hard. It would be interesting to investigate their exact complexity class, and a good candidate for these languages is the class DP. The techniques that would be used to prove it would most likely be novel for abduction-related problems. Parametrized complexity.We have investigated the parametrized complexity of representative abduc- tion with different parameters, namelyk(the Hamming distance),|H|,|M|, and|S|(size of the represen- tative set). For parameter|H|we have established a complete classification, obtained FPT-results for a large portion of languages (Schaefer languages), and proven hardness for the rest. We have established a para-coNP-hardness result for the majority of languages for parameter|M|. In our opinion, the parame- terskand|S|are perhaps the most interesting ones. For parameter|S|we have established both hardness for a large portion of the lattice, but also non-trivial FPT results forEP − -languages, but which still leaves some interesting open cases for complementive and affine languages. Finally, for parameterkwe have established non-trivial coW[1]-hardness results for languagesIMandEN − , leaving what are perhaps the most interesting open cases for future research. The parametrized complexity approach seems to us to be extremely interesting. It establishes possibly useful FPT results, as well as interesting reductions for proving hardness, and it links our problem to know problems from coding theory. Relation to coding theory.We have established a strong connection between our representative abduc- tion problem and the covering radius problem from coding theory, that as far as we know has not been established before. A lot of classical and parametrized complexity results from coding theory were instru- mental to our lattice classifications, such as NP-completeness of the covering radius problem [18] and the FPT result for the closest string problem with parameter|C|[19]. Future research on parametrized complexity with parameterkfor representative abduction and parameterr(radius) for the covering radius problem, will greatly benefit both fields. J. Schmidt, M. Maizia, V. Lagerkvist & J.K. Fichte13 References [1] Christian Alrabbaa, Sebastian Rudolph & Lukas Schweizer (2018):Faceted Answer-Set Navigation. In: Proc. RuleML+R’18 , p. 211–225, doi:10.1007/978-3-319-99906-7_14. [2] Julien Baste, Michael R. Fellows, Lars Jaffke, Tom ́as Masaˇr ́ık, Mateus de Oliveira Oliveira, Geevarghese Philip & Frances A. Rosamond (2020):Diversity of Solutions: An Exploration Through the Lens of Fixed- Parameter Tractability Theory. In:Proc. IJCAI, p. 1119–1125, doi:10.24963/IJCAI.2020/156. [3] Elisa B ̈ohl, Sarah Alice Gaggl & Dominik Rusovac (2023):Representative answer sets: Collecting some- thing of everything. In: ECAI, IOS Press, p. 271–278, doi:10.3233/FAIA230280. [4] Elmar B ̈ohler, Steffen Reith, Henning Schnoor & Heribert Vollmer (2005):Bases for Boolean co-clones.Inf. Process. Lett. 96(2), p. 59–66, doi:10.1016/j.ipl.2005.06.003. [5] Stephen A. Cook (1971):The Complexity of Theorem-Proving Procedures. In Michael A. Harrison, Ranan B. Banerji & Jeffrey D. Ullman, editors: STOC, ACM, p. 151–158, doi:10.1145/800157.805047. [6] Nadia Creignou, Uwe Egly & Johannes Schmidt (2014):Complexity Classifications for Logic-Based Argu- mentation.ACM Trans. Comput. Log.15(3), p. 19:1–19:20, doi:10.1145/2629421. [7] Nadia Creignou, Markus Kr ̈oll, Reinhard Pichler, Sebastian Skritek & Heribert Vollmer (2019):A complexity theory for hard enumeration problems. Discrete Applied Mathematics268, p. 191–209, doi:10.1016/j. dam.2019.02.025. [8] Nadia Creignou, Fr ́ed ́eric Olive & Johannes Schmidt (2023):Complexity of Reasoning with Cardinality Minimality Conditions. In Brian Williams, Yiling Chen & Jennifer Neville, editors: Proc. AAAI, AAAI Press, p. 3932–3940, doi:10.1609/AAAI.V37I4.25507. [9] Wang-Zhou Dai, Qiuling Xu, Yang Yu & Zhi-Hua Zhou (2019):Bridging Machine Learning and Logical Reasoning by Abductive Learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch ́e-Buc, E. Fox & R. Garnett, editors: NeurIPS’19, 32, Curran Associates, Inc. [10] Finnur Dells ́en (2024):Abductive Reasoning in Science. Elements in the Philosophy of Science, Cambridge University Press, doi:10.31577/orgf.2026.33106. [11] Rodney G Downey, Michael R Fellows et al. (2013):Fundamentals of parameterized complexity. 4, Springer, doi:10.1007/978-1-4471-5559-1. [12] Thomas Eiter, Esra Erdem, Halit Erdogan & Michael Fink (2013):Finding similar/diverse solutions in answer set programming. Theory and Practice of Logic Programming13(3), p. 303–359, doi:10.1017/ S1471068411000548. [13] Thomas Eiter & Georg Gottlob (1995):The complexity of logic-based abduction.J. ACM42(1), p. 3–42, doi:10.1145/200836.200838. [14] Michael R. Fellows, Andreas Pfandler, Frances A. Rosamond & Stefan R ̈ummele (2012):The Parameterized Complexity of Abduction. In: Proc. AAAI, AAAI Press, p. 743–749, doi:10.1609/AAAI.V26I1.8224. [15] J. Fichte, N. Fr ̈ohlich, M. Hecher, V. Lagerkvist, Y. Mahmood, A. Meier & J. Persson (2025):Facets in Argumentation: A Formal Approach to Argument Significance. In: Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , ijcai.org, doi:10.24963/IJCAI.2025/500. [16] Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip & Danil Sagunov (2020):Diverse Pairs of Matchings. In Yixin Cao, Siu-Wing Cheng & Minming Li, editors:31st International Symposium on Al- gorithms and Computation (ISAAC 2020) ,Leibniz International Proceedings in Informatics (LIPIcs)181, Schloss Dagstuhl–Leibniz-Zentrum f ̈ur Informatik, p. 26:1–26:12, doi:10.4230/LIPIcs.ISAAC.2020. 26. [17] Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip & Saket Saurabh (2021):Diverse Col- lections in Matroids and Graphs. In Markus Bl ̆aser & Benjamin Monmege, editors: 38th International Sym- posium on Theoretical Aspects of Computer Science (STACS 2021) ,Leibniz International Proceedings in Informatics (LIPIcs) 187, Schloss Dagstuhl–Leibniz-Zentrum f ̈ur Informatik, p. 31:1–31:14, doi:10.4230/ LIPIcs.STACS.2021.31. 14Representative Sets in Propositional Abduction [18] Moti Frances & Ami Litman (1997):On covering problems of codes.Theory of Computing Systems30(2), p. 113–119, doi:10.1007/BF02679443. [19] Jens Gramm, Rolf Niedermeier & Peter Rossmanith (2003):Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems. Algorithmica37(1), p. 25–42, doi:10.1007/S00453-003-1028-3. [20] Emmanuel Hebrard, Brahim Hnich, Barry O’Sullivan & Toby Walsh (2005):Finding Diverse and Similar Solutions in Constraint Programming. In: Proc. AAAI, p. 372–377. [21] Miki Hermann & Reinhard Pichler (2010):Counting complexity of propositional abduction. Journal of Computer and System Sciences 76(7), p. 634–649, doi:10.1016/j.jcss.2009.12.001. [22] Wen-Chao Hu, Wang-Zhou Dai, Yuan Jiang & Zhi-Hua Zhou (2025):Efficient Rectification of Neuro- Symbolic Reasoning Inconsistencies by Abductive Reflection. In: AAAI, p. 17333–17341, doi:10.1609/ aaai.v39i16.33905. [23] Alexey Ignatiev, Nina Narodytska & Joao Marques-Silva(2019):Abduction-based explanations for Machine Learning models. In: Proc. AAAI, AAAI Press, doi:10.1609/aaai.v33i01.33011511. [24] Yasir Mahmood, Arne Meier & Johannes Schmidt (2021):Parameterized complexity of abduction in Schae- fer’s framework. J. Log. Comput.31(1), p. 266–296, doi:10.1093/LOGCOM/EXAA079. [25] Yasir Mahmood, Arne Meier & Johannes Schmidt (2023):Parameterized Complexity of Logic-based Ar- gumentation in Schaefer’s Framework. ACM Trans. Comput. Log.24(3), p. 26:1–26:25, doi:10.1145/ 3582499. [26] Neeldhara Misra, Harshil Mittal & Ashutosh Rai (2024):On the Parameterized Complexity of Diverse SAT. In: ISAAC, Dagstuhl, p. 50:1–50:18, doi:10.4230/LIPICS.ISAAC.2024.50. [27] Gustav Nordh & Bruno Zanuttini (2008):What makes propositional abduction tractable.Artif. Intell. 172(10), p. 1245–1284, doi:10.1016/j.artint.2008.02.001. [28] Dominik Rusovac, Markus Hecher, Martin Gebser, Sarah Alice Gaggl & Johannes K. Fichte (2024):Navi- gating and Querying Answer Sets: How Hard Is It Really and Why?In: Proc. of KR, p. 642–653, doi:10. 24963/kr.2024/60. [29] Thomas J. Schaefer (1978):The complexity of satisfiability problems. In:Proc. STOC, ACM, p. 216–226, doi:10.1145/800133.804350. [30] J. Schmidt, M. Maizia, V. Lagerkvist & J. Fichte (2025):Complexity of Faceted Explanations in Propo- sitional Abduction. Theory and Practice of Logic Programming25(4), p. 775–793, doi:10.1017/ S1471068425100215. [31] Jinqiang Yu, Alexey Ignatiev, Peter J. Stuckey, Nina Narodytska & Joao Marques-Silva (2023):Eliminating the Impossible, Whatever Remains Must Be True: On Extracting and Applying Background Knowledge in the Context of Formal Explanations. In: Proc. AAAI, p. 4123–4131, doi:10.1609/aaai.v37i4.25528.

Instant research discovery