# Some Computational Problems Related to Pseudo-intents

From International Center for Computational Logic

# Some Computational Problems Related to Pseudo-intents

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

Barış Sertkaya

In Sébastien Ferré and Sebastian Rudolph, eds.,

**Some Computational Problems Related to Pseudo-intents**In Sébastien Ferré and Sebastian Rudolph, eds.,

*Proceedings of the 7th International Conference on Formal Concept Analysis, (ICFCA 2009)*, volume 5548 of Lecture Notes in Artificial Intelligence, 130-145, 2009. Springer**Kurzfassung****Abstract**

We investigate the computational complexity of several decision, enumeration and counting problems related to pseudo-intents. We show that given a formal context and a subset of its set of pseudo-intents, checking whether this context has an additional pseudo-intent is in coNP, and it is at least as hard as checking whether a given simple hypergraph is not saturated. We also show that recognizing the set of pseudo-intents is also in coNP, and it is at least as hard as identifying the minimal transversals of a given hypergraph. Moreover, we show that if any of these two problems turns out to be coNP-hard, then unless P = NP, pseudo-intents cannot be enumerated in output polynomial time. We also investigate the complexity of finding subsets of a given Duquenne-Guigues Base from which a given implication follows. We show that checking the existence of such a subset within a specified cardinality bound is NP-complete, and counting all such minimal subsets is #P-complete.**Forschungsgruppe:****Research Group:**Automatentheorie

```
@inproceedings{ Sert09,
author = {Bar\i{}\c{s} {Sertkaya}},
booktitle = {Proceedings of the 7th International Conference on {F}ormal {C}oncept {A}nalysis, {(ICFCA 2009)}},
editor = {S\'ebastien {Ferr\'e} and Sebastian {Rudolph}},
pages = {130--145},
publisher = {Springer Verlag},
series = {Lecture Notes in Artificial Intelligence},
title = {Some Computational Problems Related to Pseudo-intents},
volume = {5548},
year = {2009},
}
```