Počet záznamů: 1

Boolean Functions with a Simple Certificate for CNF Complexity

  1. 1.
    0351382 - UIVT-O 2013 RIV NL eng J - Článek v odborném periodiku
    Čepek, O. - Kučera, P. - Savický, Petr
    Boolean Functions with a Simple Certificate for CNF Complexity.
    Discrete Applied Mathematics. Roč. 160, 4-5 (2012), s. 365-382 ISSN 0166-218X
    Grant CEP: GA MŠk(CZ) 1M0545
    Grant ostatní: GA ČR(CZ) GP201/07/P168; GA ČR(CZ) GAP202/10/1188
    Výzkumný záměr: CEZ:AV0Z10300504
    Klíčová slova: Boolean functions * CNF representations
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.718, rok: 2012

    In this paper we study relationships between CNF representations of a given Boolean function and its essential sets of implicates. It is known that every CNF representation and every essential set must intersect. Therefore the maximum number of pairwise disjoint essential sets provides a lower bound on the size of any CNF representation. We are interested in functions, for which this lower bound is tight, and call such functions coverable. We prove that for every coverable function there exists a polynomially verifiable certificate for its minimum CNF size. On the other hand, we show that not all functions are coverable and construct examples of non-coverable functions. Moreover, we prove that computing the lower bound, i.e. the maximum number of pairwise disjoint essential sets, is NP-hard under various restrictions on the function and on its input representation.
    Trvalý link: http://hdl.handle.net/11104/0191148