Number of the records: 1
Boolean Functions with a Simple Certificate for CNF Complexity
- 1.
SYSNO ASEP 0351382 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Boolean Functions with a Simple Certificate for CNF Complexity Author(s) Čepek, O. (CZ)
Kučera, P. (CZ)
Savický, Petr (UIVT-O) SAI, RID, ORCIDSource Title Discrete Applied Mathematics. - : Elsevier - ISSN 0166-218X
Roč. 160, 4-5 (2012), s. 365-382Number of pages 18 s. Language eng - English Country NL - Netherlands Keywords Boolean functions ; CNF representations Subject RIV BA - General Mathematics R&D Projects 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10300504 - UIVT-O (2005-2011) UT WOS 000301211100002 EID SCOPUS 84856084445 DOI 10.1016/j.dam.2011.05.013 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2013
Number of the records: 1