Boolean functions with a simple certificate for CNF complexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10126211" target="_blank" >RIV/00216208:11320/12:10126211 - isvavai.cz</a>
Alternative codes found
RIV/67985807:_____/12:00351382
Result on the web
<a href="http://dx.doi.org/10.1016/j.dam.2011.05.013" target="_blank" >http://dx.doi.org/10.1016/j.dam.2011.05.013</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2011.05.013" target="_blank" >10.1016/j.dam.2011.05.013</a>
Alternative languages
Result language
angličtina
Original language name
Boolean functions with a simple certificate for CNF complexity
Original language description
In this paper we study relationships between CNF representations of a given Boolean function f and essential sets of implicates off. It is known that every CNF representation and every essential set must intersect. Therefore the maximum number of pairwise disjoint essential sets off provides a lower bound on the size of any CNF representation off. We are interested in functions, for which this lower bound is tight, and call such functions coverable. We prove that for every covetable function there exists a polynomially verifiable certificate (witness) for its minimum CNF size. On the other hand, we show that not all functions are covetable, and construct examples of non-covetable 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discrete Applied Mathematics
ISSN
0166-218X
e-ISSN
—
Volume of the periodical
160
Issue of the periodical within the volume
4-5
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
18
Pages from-to
365-382
UT code for WoS article
000301211100002
EID of the result in the Scopus database
—