On the intractability of computing the Duquenne-Guigues base
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).
implication base computational complexity