Complexity of verifying complete meet-irreducible lists
Follow the latest progress by email.
Given a finite implication closure system and an irredundant list of genuine meet-irreducibles, how hard is it to decide whether the list is complete? The restricted target allows acyclic implications with at most three premises.
Why it matters and what counts as progress
Why it matters: Completeness testing is shared by implication systems, Horn descriptions and related closure representations, even when every supplied member is genuine.
What counts as progress: Prove a complexity classification under these restrictions, or give a faster completeness test for a precisely defined subclass.
How the problem developed
- 1995 · Partial result [1]
Ravi Khardon Related Horn-formula and characteristic-model translations were shown equivalent to completeness of a proposed model list; the exact complexity remained open.
- 2025 · Open problem [1]
Researchers at ISAAC Enumeration of irreducible closed sets from implications was still described as widely open, including for acyclic convex geometries.
- 20 Jul 2026 · Reported claim [1]
Mikhail Babin Proved coNP-completeness of testing whether implication and intersection specifications define the same closure system, with hardness under acyclic bounded-premise restrictions.
AI contribution
Completeness of Canonical Closure Representations Is coNP-Complete
Testing whether a supplied family of meet-irreducibles is the complete canonical family of a finite implication closure system is coNP-complete, even with acyclic implications of premise size at most three and a genuine irredundant supplied family. The hard direction reduces 3-UNSAT to a missing member.
Sources
Website timeline
Publication dates and editorial changes.
GPT-assisted proof classifies closure-list completeness as coNP-complete