Počet záznamů: 1
Boolean Functions with a Simple Certificate for CNF Complexity
- 1.
SYSNO ASEP 0351382 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Boolean Functions with a Simple Certificate for CNF Complexity Tvůrce(i) Čepek, O. (CZ)
Kučera, P. (CZ)
Savický, Petr (UIVT-O) SAI, RID, ORCIDZdroj.dok. Discrete Applied Mathematics. - : Elsevier - ISSN 0166-218X
Roč. 160, 4-5 (2012), s. 365-382Poč.str. 18 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova Boolean functions ; CNF representations Vědní obor RIV BA - Obecná matematika CEP 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10300504 - UIVT-O (2005-2011) UT WOS 000301211100002 EID SCOPUS 84856084445 DOI 10.1016/j.dam.2011.05.013 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2013
Počet záznamů: 1