
Coverable functions: hardness results
 Petr Kucera
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 NPcomplete to
compute ess(f) provided f is a Horn function
given by a Horn CNF, and that it is NPhard to compute ess(f)
provided f is a general Boolean function given by its truthtable.

