Pseudo-Closed Family Verification is NP-Complete (Or: How Claude Helped Tackle Bernhard’s Problem)
From International Center for Computational Logic
Pseudo-Closed Family Verification is NP-Complete (Or: How Claude Helped Tackle Bernhard’s Problem)
Talk by Sebastian Rudolph
- Location: APB 3027
- Start: 8. October 2026 at 11:00 am
- End: 8. October 2026 at 12:00 pm
- Research group: Computational Logic
- Event series: Research Seminar Logic and AI
- iCal
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.
