Counting Pseudo-intents and #P-completeness.
Formal Concept Analysis:306-308, 2006.
Sergei Kuznetsov and Sergei Obiedkov.
[doi]
[abstract]
[BibTeX]
Implications of a formal context (G,M,I) have a minimal implication basis, called Duquenne-Guigues basis or stem base. It is shown that the problem of deciding whether
a set of attributes is a premise of the stem base is in coNP and determining the size of the stem base is polynomially Turingequivalent to a #P-complete problem.