# Towards the Complexity of Recognizing Pseudo-intents

From International Center for Computational Logic

# Towards the Complexity of Recognizing Pseudo-intents

##### Barış SertkayaBarış Sertkaya

Barış Sertkaya

In Frithjof Dau and Sebastian Rudolph, eds.,

**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**Kurzfassung****Abstract**

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},
}
```