• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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.