?
Computing premises of a minimal cover of functional dependencies is intractable
Discrete Applied Mathematics. 2013. Vol. 161. No. 6. P. 742-749.
Kuznetsov S., Babin M. A.
The problem of recognizing whether a subset of attributes is a premise of a minimal cover of functional dependencies of a relation is shown to be coNP-complete. The complexity of some related decision, enumerating, and sampling problems on functional dependencies, FCA implications, and closed sets of attributes is discussed.