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

Kuznetsov, Sergei O.

J. UCS 10, No. 8, 927-933 (2004).

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)

Keywords:

computational complexity; implication base