Towards the Complexity of Recognizing Pseudo-intents

Barış SertkayaBarış Sertkaya

Download

Barış Sertkaya
Towards the Complexity of Recognizing Pseudo-intents
In Frithjof Dau and Sebastian Rudolph, eds., Proceedings of the 17th International Conference on Conceptual Structures, (ICCS 2009), volume 5662, 284-292, 2009

Details
Bibtex

KurzfassungAbstract
Pseudo-intents play a key role in Formal Concept Analysis. They form the premises of the implications in the Duquenne-Guigues Base, which is a minimum cardinality base for the valid implications of a formal context. It has been shown that checking whether a set is a pseudo-intent is in coNP. However, it is still open whether this problem is coNP-hard, or it is solvable in polynomial time. In the current work we prove a first lower bound for this problem by showing that it is at least as hard as TRANSVERSAL HYPERGRAPH, which is the problem of checking whether the edges of a given hypergraph are precisely the minimal transversals of another given hypergraph. This is a prominent open problem in hypergraph theory that is conjectured to form a complexity class properly contained between P and coNP. Our result partially explains why the attempts in the FCA community for finding a polynomial algorithm for recognizing pseudo-intents have failed until now. We also formulate a decision problem, namely FIRST PSEUDO-INTENT, and show that if this problem is not polynomial, then, unless P = NP, pseudo-intents cannot be enumerated with polynomial delay in lexicographic order.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Sert09c,
  author = {Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Proceedings of the 17th International Conference on {C}onceptual {S}tructures, {(ICCS 2009)}},
  editor = {Frithjof {Dau} and Sebastian {Rudolph}},
  pages = {284--292},
  title = {Towards the Complexity of Recognizing Pseudo-intents},
  volume = {5662},
  year = {2009},
}