# 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

Technical Report,

**Some Computational Problems Related to Pseudo-intents**Technical Report,

*Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology*, volume LTCS-08-06, 2008.*LTCS-Report***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 set of its 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 saturated. We also show that recognizing the set of pseudo-intents is also in coNP and it is at least as hard as checking whether a given hypergraph is the transversal hypergraph of another 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.**Bemerkung:****Note:**See http://lat.inf.tu-dresden.de/research/reports.html.**Forschungsgruppe:****Research Group:**AutomatentheorieAutomata Theory

```
@techreport{ sert-08-06,
address = {Germany},
author = {Bar{\i}{\c{s}} {Sertkaya}},
institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
number = {LTCS-08-06},
title = {Some Computational Problems Related to Pseudo-intents},
type = {LTCS-Report},
year = {2008},
}
```