Publication at Faculty of Mathematics and Physics |
2020
Abstract
Horn functions form a subclass of Boolean functions and ap-pear in many different areas of computer science and math-ematics as a general tool to describe implications and de-pendencies. Finding minimum sized representations for suchfunctions with respect to most commonly used measures is acomputationally hard problem that remains hard even for theimportant subclass of key Horn functions.
In this paper weprovide logarithmic factor approximation algorithms for keyHorn functions with respect to all measures studied in the lit-erature for which the problem is known to be hard.