×

On the intractability of computing the Duquenne-Guigues base. (English) Zbl 1277.68258

Summary: Implications of a formal context \((G,M,I)\) obey Armstrong rules, which allows for definition of a minimal (in the number of implications) implication base, called Duquenne-Guigues or stem base in the literature. A long-standing problem was that of an upper bound for the size of a stem base in the size of the relation \(I\). In this paper we give a simple example of a relation where this boundary is exponential. We also prove \(\#\)P-hardness of the problem of determining the size of the stem base (i.e., the number of pseudo-intents).

MSC:

68T30 Knowledge representation
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
06A15 Galois correspondences, closure operators (in relation to ordered sets)
PDF BibTeX XML Cite
Full Text: Link