🤖 AI

Representative Sets in Propositional Abduction

This paper investigates the computational complexity of determining whether a given set of explanations in propositional abduction can represent any other explanation within a bounded symmetric difference, providing a complete classical complexity classification and a parameterized analysis that reveals a novel connection to the covering radius problem in coding theory.

Original authors: Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, Johannes K. Fichte

Published 2026-07-24

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, Johannes K. Fichte

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of just finding one suspect, you need to understand the entire landscape of possible culprits. This is the world of propositional abduction, a branch of artificial intelligence and logic where computers try to figure out the best explanation for an observation. Think of it like a doctor looking at a patient with a high fever. The doctor knows a few rules: "If the patient has a weak immune system and a bacterial infection, they get a fever," or "If they have a weak immune system and a virus, they get a fever." The fever is the "manifestation" (the clue), and the doctor must guess the "hypotheses" (the underlying causes) that fit the rules.

Usually, the goal is just to find one good explanation. But what if you want to know if your list of suspects is complete? What if you want to know if a small group of explanations can "represent" or stand in for all the other possible explanations? This is where the math gets tricky. The paper explores whether a small, curated list of explanations can cover the entire universe of possibilities within a certain "distance" (like how different two explanations are from each other). It's like asking: "If I have a map with just five key landmarks, can I get to any other spot in the city within a 10-minute walk?" The authors dive deep into the computer science of this question, using a framework called Post's Lattice (a giant map of all possible logical rule sets) to see which types of rules make this easy and which make it a nightmare for computers.

The Paper's Big Discovery: The "Representative Set" Hunt

In this paper, the authors Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, and Johannes K. Fichte tackle a new, slightly more complex version of the abduction problem. They call it REPABD. Instead of just asking, "Is there an explanation?", they ask, "Does this specific set of explanations, $S$ , represent every other possible explanation within a certain distance $k$ ?"

To visualize this, imagine you are packing for a trip. You have a massive closet full of outfits (all possible explanations). You only have room for a small suitcase (your set $S$ ). The question is: Can you pick a few outfits for your suitcase such that for any outfit you didn't pack, there is one in your suitcase that is very similar to it (within distance $k$ )? If you can do this, your suitcase is "representative."

The Complexity Map: Easy vs. Impossible

The authors spent a lot of time classifying exactly when this problem is easy for computers to solve and when it becomes hopelessly hard. They used a "dictionary" of logical rules (constraint languages) to test every possible scenario.

The Hard Truth: For most types of logical rules, finding or verifying a representative set is incredibly difficult. The authors proved that for many common rule sets, the problem is coNP-hard or even $\Pi^P_2$ -complete. In plain English, this means that as the number of clues and rules grows, the time it takes for a computer to solve this explodes. It's not just "hard"; it's in a class of problems that are likely impossible to solve quickly for large inputs.
The Rare Islands of Ease: Surprisingly, they found a few tiny islands where the problem is solvable quickly (in polynomial time). These happen only when the logical rules are very specific and simple, such as "strictly essentially positive" or "strictly essentially negative" rules. In these cases, the logic is so constrained that the computer can quickly figure out if your small set of explanations covers everything.
The "Subset-Minimal" Twist: The authors also looked at a stricter version where they only care about the simplest explanations (those with no unnecessary parts). They found that this version is actually slightly easier in some cases, but it still hits a wall of difficulty if the rules allow for "equality" (where two things must be the same).

The Coding Theory Connection: A Surprising Link

One of the most fascinating parts of the paper is a connection the authors discovered between their logic puzzle and coding theory (the math behind error-correcting codes used in Wi-Fi and space communication).

They realized that their problem is mathematically identical to the Covering Radius Problem. Imagine you have a set of secret codes (your explanations). The "covering radius" asks: "Is there any possible message that is too far away from all the codes in your set?" If the answer is "no," then your set covers the whole space.

The authors showed that if you can solve the representative set problem for certain logical rules, you can also solve the covering radius problem.
Conversely, if the covering radius problem is hard (which it is, for many cases), then the representative set problem is hard too.
This is a brand-new link between non-monotonic reasoning (how we change our minds when we get new info) and coding theory. The authors suggest that this connection is crucial for understanding the limits of these problems.

What About "Parameters"? (The "Small" Variables)

Since the problem is so hard in general, the authors asked: "What if we fix one specific number to be small?" This is called parameterized complexity. They tested four different numbers:

$k$ (The distance): How close the explanations need to be.
$|H|$ (The number of hypotheses): How many possible causes there are.
$|M|$ (The number of manifestations): How many symptoms we are observing.
$|S|$ (The size of the representative set): How many explanations are in our "suitcase."

Their findings here were mixed but insightful:

$|H|$ (Number of hypotheses): If the number of possible causes is small, the problem becomes easy (solvable) for many types of rules. You can just check every combination.
$|S|$ (Size of the set): If the number of explanations in your suitcase is small, the problem is easy only if the rules are very simple (strictly positive). For other rules, it remains hard.
$k$ (Distance): This turned out to be the trickiest. Even if the distance $k$ is small, the problem remains very hard (coW[1]-hard) for many rule sets. The authors couldn't fully solve this for every case, leaving it as an open mystery for future researchers.

What They Didn't Solve (The Open Questions)

The paper is honest about what it doesn't know.

They couldn't fully classify the complexity for "1-valid" languages (rules that are always true if everything is true). They suspect these are very hard (likely in a class called DP), but they didn't prove it.
They also noted that a complete classification for the parameter $k$ (distance) would require solving the parameterized complexity of the covering radius problem, which is currently an open problem in coding theory. So, until coding theorists solve that, the logic puzzle remains partially unsolved.

The Takeaway

This paper doesn't give us a magic button to instantly generate perfect explanations for every medical diagnosis or mystery. Instead, it draws a very precise map of where the difficulty lies. It tells us that while we can sometimes find a small, representative group of explanations quickly, for most real-world logical setups, the task is computationally brutal.

The most exciting part is the bridge they built to coding theory. By showing that "representative sets" in logic are the same as "covering radius" in codes, they've opened a door for two different fields of science to help each other. If coding theorists find a faster way to check covering radii, logic researchers might suddenly find a faster way to check representative sets, and vice versa. For now, the authors have shown us that the path to understanding the "space of explanations" is paved with both easy shortcuts and deep, unsolved canyons.

Technical Summary: Representative Sets in Propositional Abduction

Problem Definition
The paper investigates the Representative Abduction Problem (REPABD), a decision problem concerning the structure of the solution space in propositional abduction. In standard propositional abduction, given a knowledge base ($KB$), a set of hypotheses ( $H$ ), and a manifestation ( $M$ ), the goal is to find an explanation $E \subseteq H$ such that $KB \land E$ is satisfiable and $KB \land E \models M$ .

This work shifts focus from finding individual explanations to analyzing the coverage of a set of explanations. Specifically, given a distance metric defined by the symmetric difference (Hamming distance) $d(E_1, E_2) = |E_1 \triangle E_2|$ , and a parameter $k \geq 0$ , the problem asks whether a given set of explanations $S$ is $k$ -representative. A set $S$ is $k$ -representative if every possible explanation $E$ (or every subset-minimal explanation in the variant REPABD $_\subseteq$ ) is within Hamming distance $k$ of at least one element in $S$ . Formally, $S$ is $k$ -representative if $\bigcup_{E \in S} \{E' \in \mathcal{E}(I) \mid d(E, E') \leq k\} = \mathcal{E}(I)$ .

Methodology
The authors employ a fine-grained complexity analysis based on Post's lattice of Boolean constraint languages.

Constraint Languages ( $\Gamma$ ): The knowledge base is restricted to conjunctive formulas where atoms are relations from a set $\Gamma$ . The complexity is classified for all possible choices of $\Gamma$ .
Algebraic Tools: The paper utilizes primitive positive definitions (pp-definability) and equality-free pp-definitions (efpp) to establish reducibility between different constraint languages. Key algebraic concepts include co-clones, relational clones, and the distinction between relations that are prime, irredundant, or constant.
Complexity Frameworks:
- Classical Complexity: The problem is analyzed within the Polynomial Hierarchy (PH), specifically looking for membership in P, coNP, NP, $\Pi^P_2$ , and $\Sigma^P_2$ .
- Parameterized Complexity: The problem is analyzed with respect to parameters $k$ (distance), $|H|$ (hypotheses), $|M|$ (manifestations), and $|S|$ (size of the representative set). The study uses the W-hierarchy (e.g., W[1]-hardness) and FPT (Fixed-Parameter Tractable) classifications.
Reductions: The authors establish connections to coding theory problems, specifically the Covering Radius Problem and the Closest String Problem, to derive hardness and tractability results.

Key Contributions and Results

1. Classical Complexity Classification
The paper provides a complete classification for REPABD( $\Gamma$ ) and REPABD $_\subseteq$ ( $\Gamma$ ):

$\Pi^P_2$ -Completeness: If $\Gamma$ can express certain non-trivial relations (specifically involving $IN_2$ or $II_0$ within $II_2$ ), the problem is $\Pi^P_2$ -complete.
coNP-Hardness/Completeness: For many fragments where standard abduction (ABD) is tractable (e.g., Horn, dual-Horn, affine, 2-CNF), REPABD is coNP-hard or coNP-complete. This is notably driven by the ability to express the "trivial" unary relation $t = \{(0), (1)\}$ or specific non-constant relations.
Tractability (P):
- For REPABD( $\Gamma$ ), the problem is in P only in very restricted cases where the constraint language is trivial (e.g., containing only constant relations).
- For the subset-minimal variant REPABD $_\subseteq$ ( $\Gamma$ ), the paper identifies a broader class of tractable cases. If $\Gamma$ consists of strictly essentially positive (EP $^-$ ) or strictly essentially negative (EN $^-$ ) clauses (and equality cannot be expressed), the problem is solvable in polynomial time. In these cases, there is often a unique subset-minimal explanation, making the verification of the representative set trivial.

2. Parameterized Complexity
The authors analyze the problem under various parameters:

Parameter $k$ (Distance): The problem is generally hard. It is coW[1]-hard for languages containing implication ($IM$) or specific negative clauses ( $IS^2_1$ ). The complexity of REPABD( $\Gamma$ , $k$ ) for essentially positive languages is shown to be FPT-equivalent to the Covering Radius Problem (parameterized by radius $r$ ).
Parameter $|H|$ (Hypotheses): A dichotomy is established. If $\Gamma$ is a Schaefer language (Horn, dual-Horn, affine, or 2-CNF), the problem is FPT (solvable in $f(|H|) \cdot poly(n)$ time) via brute-force enumeration of subsets. Otherwise, it is para-coDP-hard or para-NP-hard.
Parameter $|M|$ (Manifestations): The problem is para-coNP-hard for any language where the trivial relation $t$ or the constant relation $T$ can be expressed.
Parameter $|S|$ (Size of Representative Set):
- The problem is para-coNP-hard for languages containing specific positive clauses ( $IS^2_{11}$ ).
- For strictly essentially positive languages (EP $^-$ ), the problem is FPT. The authors prove this by reducing the problem to the Closest String Problem, which is known to be FPT with respect to the number of strings.

Significance and Claims
The paper claims to provide the first fine-grained complexity classification of representative sets in propositional abduction. Its primary contributions are:

Complexity Gap: It demonstrates that while standard abduction is $\Sigma^P_2$ -complete, the problem of verifying representative sets often drops to $\Pi^P_2$ -complete or coNP-complete, but rarely to P, except for very specific structural restrictions on the knowledge base.
Tractability in Subsets: It reveals that the subset-minimal variant (REPABD $_\subseteq$ ) is significantly more tractable than the general variant for essentially positive/negative languages, a result not immediately obvious from the general case.
Connection to Coding Theory: The paper establishes a novel link between non-monotonic reasoning and coding theory. It shows that a full parameterized classification of REPABD depends on resolving the parameterized complexity of the Covering Radius Problem. Conversely, it utilizes the FPT status of the Closest String Problem to prove FPT results for representative abduction.
Open Problems: The authors note that the exact complexity of 1-valid languages remains open (suspected to be DP-complete) and that the parameterized complexity of the Covering Radius Problem is a critical bottleneck for a complete classification of the parameter $k$ .

The work concludes that asking "fine-grained" questions about the solution space (such as coverage and diversity) introduces computational challenges distinct from finding single solutions, often requiring tools from algebraic logic and coding theory to resolve.