Pseudo-Closed Family Verification is NP-Complete (Or: How Claude Helped Tackle Bernhard’s Problem)

Sebastian RudolphSebastian Rudolph

Download

Sebastian Rudolph
Pseudo-Closed Family Verification is NP-Complete (Or: How Claude Helped Tackle Bernhard’s Problem)
Conceptual Knowledge Structures, volume 16811 of LNCS, to appear. Springer

Details
Bibtex

KurzfassungAbstract
Every closure operator on a finite set admits a canonical minimum implication basis – the stem base or Duquenne--Guigues base – whose premises are the pseudo-closed sets. The Pseudo-Closed Family problem (PCF) asks whether a given family of sets equals the pseudo-closed sets of some closure operator. We prove that PCF is NP-complete, negatively answering a question posed by Bernhard Ganter at CONCEPTS'25, which essentially asked for ``easy ways to verify PCF. As the large language model Claude Opus 4.6 was instrumental in establishing the NP-hardness part, this paper also discusses the methodology applied and observations made in the process.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

The final publication is available at Springer.

@inproceedings{R2026,
  author    = {Sebastian Rudolph},
  title     = {Pseudo-Closed Family Verification is {NP-Complete} (Or: How
               Claude Helped Tackle Bernhard’s Problem)},
  booktitle = {Conceptual Knowledge Structures},
  series    = {LNCS},
  volume    = {16811},
  publisher = {Springer},
  year      = {2026}
}