Pseudo-Closed Family Verification is NP-Complete (Or: How Claude Helped Tackle Bernhard’s Problem)
Aus International Center for Computational Logic
Pseudo-Closed Family Verification is NP-Complete (Or: How Claude Helped Tackle Bernhard’s Problem)
Vortrag von Sebastian Rudolph
- Veranstaltungsort: APB 3027
- Beginn: 8. Oktober 2026 um 11:00
- Ende: 8. Oktober 2026 um 12:00
- Forschungsgruppe: 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.
