Coverable functions: hardness results
- Petr Kucera
||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.
Last updated: November 7, 2009.