Source-linked AI summary
Choosing What to Observe: Higher-Order Obstructions in Horn Abduction
Yukun Yang
TL;DR
The paper asks how to choose hypotheses when contexts are only partially observed and explanations may vary across contexts. It characterizes sufficient observations using minimal context families with no common explanation, then establishes complexity and representation boundaries for that framework.
Problem
An explanation may exist in every complete context yet be impossible to select from the information observed, so the paper asks which source variables make one valid hypothesis choice possible for every report.
Source: §1 · p. 1Method
The paper characterizes failure through minimal context families with empty explanation intersection and uses their variable spans as hypergraph edges whose transversals are exactly the sufficient observation sets.
Source: §1 · p. 1Results
Takeaways & Limitations
The framework connects explanatory choice to information requirements and representation cost, with exact contracts that compose across independent components.
Source: §1 · p. 1, §7 · p. 7Contexts, explanations, and contracts may each require exponential space, and the tabulated bound excludes their construction; guarantees also assume simultaneous exact Boolean observations over the supplied context space.
Source: §5.4 · p. 6, §6.3 · p. 7
Abstract
from arXiv · showhide
An explanation may exist in every complete context yet be impossible to select from the information observed. We study this distinction in finite propositional Horn abduction with integrity constraints. Observations are sufficient when each report admits one hypothesis set that is consistent and entails the manifestation in every compatible context. We characterize sufficiency by minimal context families with no common explanation. Their variable spans form a canonical hypergraph whose transversals are exactly the sufficient observation sets. The characterization recovers classical discernibility for unique explanations and supports composition across independent components. Minimal obstructions have unbounded cardinality even for acyclic rules, while rectangular explanation families admit a tight bound given by their largest choice domain. With circuit-defined contexts, sufficiency is $\Pi_3^P$-complete and selecting at most $k$ observable variables is $\Sigma_4^P$-complete, already for unrestricted contexts and acyclic rules. The selection reduction makes observation choices enforce globally fixed existential commitments. Explicit contexts reduce both tasks to NP-complete problems; tabulated explanation families make sufficiency polynomial. These results connect explanatory choice, information requirements, and representation cost.
1 Introduction
The paper distinguishes explanations that exist in each complete context from a single hypothesis set that can be chosen using only observed information. It characterizes sufficient observations through minimal context families with no common explanation, yielding a canonical contract and complexity results.
1 Introduction
- The three-context example shows that pairwise shared explanations do not guarantee one explanation common to all contexts, despite efficient local Horn verification.Either telemetry bit nevertheless permits a valid commitment without revealing the complete context.Source: §1 · p. 1
- Sufficient observations are exactly the variable sets that hit every edge in the canonical hypergraph formed by spans of minimal context families with no common explanation.This characterizes which source variables must be observed so each report admits one hypothesis set valid across its compatible contexts.Source: §1 · p. 1
- Uniform choice fixes hypotheses before hidden facts are known, while consistency and entailment are checked separately in each compatible context.Contextwise choices can use unavailable information, and pairwise tests assume an intersection property that arbitrary explanation families need not have.Source: §1 · p. 1
- With circuit-defined contexts, robust verification, one-cell uniform explanation existence, and sufficiency are coNP-, ΣP2-, and ΠP3-complete, respectively.Selecting at most k observable variables is ΣP4-complete; the reduction uses paired telemetry variables to enforce a globally fixed assignment.Source: §1 · p. 1
- Listed contexts make sufficiency and observation selection NP-complete, while tabulated explanation families make sufficiency polynomial but leave selection NP-complete.Minimal obstructions can be arbitrarily large under acyclic Horn rules; independent finite choice slots instead have a tight bound by domain size, and contracts compose across independent components.Source: §1 · p. 1
2 Background and Related Work
The paper places observation contracts alongside work on abduction, diagnosis, decision tables, and information-dependent decisions, while distinguishing its objective from nearby explanation and feature-selection tasks.
2 Background and Related Work
- Unlike diagnosis conflicts and truth-maintenance environments, this paper's obstructions are context families, and their transversals select observations.Classical abduction distinguishes deriving a conclusion from supplying consistent assumptions that support it.Source: §2 · p. 1
- Prior tractability results restrict the language or semantics, whereas this paper locates complexity in uniform choice across contexts despite polynomial local verification.Explanation facets describe variability within families [Schmidt et al., 2025], while this work compares intersections across contexts.Source: §2 · p. 2
- Unlike statistical learning of explanations from partial examples, the framework requires validity in every supplied possible context and studies one commitment after a fixed observation [Juba et al., 2018; Fagin et al., 2003; Reif, 1984; Rintanen, 2004].All hypothesis bits share one observation set, giving an ordinary three-block formula for sufficiency.Source: §2 · p. 2
- The rough-set construction is recovered for unique explanations, but multiple permissible explanations require compatibility beyond pairwise discernibility.The paper distinguishes selecting a common permissible decision from preserving an original decision, and from entropy-based reduct criteria.Source: §2 · p. 2
3 Observation-Aware Horn Abduction
The section formalizes contextual validity for finite Horn instances, then defines sufficiency as the existence of a uniform hypothesis choice for each observed report. Its examples distinguish that requirement from both local explanation choice and source-free proof.
3.1 Contexts and classical validity
- A contextual abduction instance specifies source variables, hypotheses, Horn rules, a derived manifestation, and possible contexts; a hypothesis set is valid when it derives the manifestation without deriving ⊥.Possible contexts encode source assignments, and the context set can capture source correlations.Source: §3.1 · p. 2
3.2 Uniformity and sufficiency
- An observation scheme groups contexts that agree on observed variables, and a uniform explanation policy assigns one hypothesis set to each realized report.That set must be valid in every context producing the report; equivalently, each cell's uniform explanation family must be nonempty.Source: §3.2 · p. 2
- Sufficiency is upward closed; no observation suffices exactly when all contexts share an explanation, while full observation suffices exactly when every context has one.An empty context space makes every scheme sufficient.Source: §3.2 · p. 2
- In the acyclic triage example, every pair of context explanation families intersects but the triple does not, although observing either variable permits valid commitments.A second example shows that the common hypothesis set {a, b} makes observation unnecessary even when locally minimal explanations differ by context.Source: §3.2 · p. 3
- Uniformity constrains the chosen hypotheses, not their deductive support: context-specific derivations can validate the same set, while allowing different sets per context would violate the information constraint.Preferences apply after the information restriction, and a selected inclusion-minimal member need not be locally minimal.Source: §3.2 · p. 3
4 Explanatory Obstructions and Observation Contracts
Minimal context sets with no common explanation yield a canonical hypergraph whose transversals exactly characterize sufficient observations. The framework recovers classical discernibility, permits unbounded obstructions under acyclic rules, and requires obstruction witnesses to update contracts after context restriction.
4.1 From failed commitments to variable requirements
- The canonical observation contract is the hypergraph of minimal-obstruction spans, and a scheme is sufficient exactly when it transverses every edge.Each obstruction must be split by an observed coordinate.Source: §4.1 · p. 3
- Minimal sufficient schemes are exactly minimal transversals, while minimum-cost sufficient schemes are minimum-cost transversals.A variable is mandatory in every sufficient scheme exactly when its singleton is a contract edge.Source: §4.1 · p. 3
4.2 Canonicality and classical correspondence
- When every context has a unique explanation, minimal obstructions are pairs with different explanations, recovering the ordinary discernibility hypergraph.Instances with the same contract have the same sufficient observation schemes, even if their policies use different hypotheses.Source: §4.2 · pp. 3–4
4.3 Obstruction size and expressive limits
- For every integer r ≥ 2, an acyclic Horn instance can have a minimal obstruction of r contexts.Neither acyclicity nor bounded rule width bounds obstruction size.Source: §4.3 · p. 4
- Every irredundant hypergraph without an empty edge is realizable as an acyclic Horn observation contract with two hypothesis atoms and at most 1 + |G| contexts.The construction has encoding size O((|G| + 1)(|X| + 1)).Source: §4.3 · p. 4
- Obstruction cardinality and variable-span size are distinct parameters, and every upward-closed observation requirement is realizable.The finite witness result bounds explanation-family size in relation to obstruction cardinality.Source: §4.3 · p. 4
4.4 Context restriction and obstruction provenance
- Every scheme sufficient before context restriction remains sufficient afterward, but the original contract alone may not determine the restricted contract.Updating may require obstruction witnesses whose larger spans were discarded from the original contract.Source: §4.4 · p. 5
- Two instances can share the full-context contract yet have different contracts after restriction to the same contexts.For the Boolean-square example, restriction yields an empty contract in one instance and {{q}} in the other.Source: §4.4 · p. 5
5 Computational Complexity and Representation
The section distinguishes the complexity of uniform explanatory choice from local Horn inference and shows that representation affects the cost of sufficiency and observation selection. Succinct contexts yield higher complexity than explicitly listed contexts or tabulated explanation families.
5.1 Decision problems and a Horn compilation lemma
- A polynomial-size acyclic Horn theory with binary rule bodies can realize circuit-defined explanation families, with valid explanations encoding complete satisfying assignments.The construction uses dual rails and selectors; auxiliary atoms are derived rather than hypotheses.Source: §5.1 · p. 5
5.2 Fixed observations
- Robust Verification is coNP-complete, Cell Existence is ΣP2-complete, and succinct Sufficiency is ΠP3-complete under the stated reductions.The lower bounds hold with no integrity constraints, acyclic Horn rules, and one manifestation.Source: §5.2 · p. 5
- Sufficiency quantifies over observed reports, one shared explanation, and hidden contexts, so the explanation may depend on observations but not on hidden facts.The lower-bound construction encodes the corresponding quantifier pattern using circuit-realized explanations.Source: §5.2 · p. 5
5.3 Choosing observations
- Observation Selection is ΣP4-complete even with no integrity constraints, acyclic rules, and rule bodies of size at most two.The reduction uses paired telemetry variables to force one globally fixed existential assignment while allowing other hypotheses to depend on reports.Source: §5.3 · pp. 5–6
5.4 Explicit representations and policy size
- For explicitly listed contexts with Horn-defined explanation families, both Sufficiency and Observation Selection are NP-complete.When explanation families are tabulated too, Sufficiency is polynomial-time decidable, while Selection remains NP-complete even with two singleton explanations available across the table.Source: §5.4 · p. 6
- Contexts, explanations, and observation contracts may each require exponential space, and the tabulated sufficiency bound excludes the cost of constructing them.Even a small obstruction rank does not make finding witness contexts and shared explanations cheap under succinct representation.Source: §5.4 · p. 6
- A polynomial-size acyclic Horn instance can require 2n distinct policy explanations under full observation, although a matching policy circuit is linear-size.The output count means a full policy table is unsuitable as a polynomial certificate in the succinct setting.Source: §5.4 · p. 6
6 Structural Fragments, Composition, and Scope
Structural conditions clarify when pairwise compatibility suffices, how independent components share observation requirements, and where the framework’s guarantees stop. Rectangular explanation families have a tight obstruction bound, while composition requires independence assumptions.
6.1 When pairwise compatibility becomes sufficient
- Pairwise-intersecting context families have a common explanation when obstruction rank is at most two, but their variable spans can still encode arbitrary Hitting Set instances.Thus pairwise witness construction does not remove the observation optimization problem.Source: §6.1 · pp. 6–7
- Rectangular explanation families have minimal obstructions of size at most the largest slot domain, and this bound is tight.For Boolean slots with nonempty individual families, sufficiency reduces to separating every pair of contexts with disjoint explanation families; acyclicity alone does not imply rectangularity.Source: §6.1 · p. 6
- For tabulated families of fixed rank r, subsets of at most r contexts suffice to compile all minimal obstructions in polynomial time, but minimum observation selection remains NP-hard at rank two..Source: §6.1 · p. 6
- Without integrity constraints, nonempty upward-closed explanation families all contain the full hypothesis set, so no observations are needed; otherwise no scheme suffices.Imposing local minimality can change this conclusion.Source: §6.1 · p. 7
6.2 Independent components share observation requirements
- Under the stated independence assumptions, an observation set is sufficient for the combined system exactly when it is sufficient for every component.Component explanations combine by union because their hypothesis and derived vocabularies are disjoint and constraints are internal.Source: §6.2 · p. 7
- In the example, combining contracts with edges {p, q} and {q, r} gives minimal observation schemes {q} and {p, r}; cross-component constraints can invalidate this composition rule.Sharing telemetry can therefore lower observation cost under the independence assumptions.Source: §6.2 · p. 7
6.3 Interpretation and limits
- The guarantee covers every context in the supplied space under simultaneous exact Boolean observations; sequential sensing, noisy reports, richer entailment, and earlier preferences require separate analysis.Hypotheses are permissible explanations, without probabilistic or causal guarantees.Source: §6.3 · p. 7
7 Conclusion
The paper characterizes uniform abductive choice through minimal context families with no common explanation and their observation contracts. Its complexity results distinguish information dependencies from polynomial Horn inference, and its paired-sensor reduction shows how observation choices enforce global commitments.
7 Conclusion
- Minimal empty-intersection context families characterize when partial observations permit a uniform abductive commitment, and their spans form canonical observation contracts.These contracts link higher-order compatibility to hypergraph transversals.Source: §7 · p. 7
- ΠP3 and ΣP4 completeness results separate information dependencies from polynomial Horn inference, while explicit representations expose lower complexity boundaries..Source: §7 · p. 7
- The paired-sensor reduction explains how choosing an information channel can enforce a global commitment despite report-dependent explanatory choices.Sequential observation and uniform preference semantics are identified as extensions for separate study.Source: §7 · p. 7