abstract

This talk is a continuation of the talk "Coverable functions: definitions and properties". In this talk we shall present three hardness results concerning the maximum number of pairwise disjoint essential sets of implicates of f (denoted by ess(f)). We show, that for every k there exists a Horn function f with a minimum number of clauses in a CNF at least k times bigger than ess(f), i.e. such that cnf(f) is at least k*ess(f). Then we show that it is NP-complete to compute ess(f) provided f is a Horn function given by a Horn CNF, and that it is NP-hard to compute ess(f) provided f is a general Boolean function given by its truth-table.