This HTML5 document contains 45 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n12http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n11http://linked.opendata.cz/resource/domain/vavai/projekt/
n15http://linked.opendata.cz/resource/domain/vavai/subjekt/
n14http://linked.opendata.cz/ontology/domain/vavai/
n17http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n20http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
n19http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F67985807%3A_____%2F12%3A00351382%21RIV13-AV0-67985807/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n7http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n9http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n6http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n16http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F67985807%3A_____%2F12%3A00351382%21RIV13-AV0-67985807
rdf:type
skos:Concept n14:Vysledek
dcterms:description
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. 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.
dcterms:title
Boolean Functions with a Simple Certificate for CNF Complexity Boolean Functions with a Simple Certificate for CNF Complexity
skos:prefLabel
Boolean Functions with a Simple Certificate for CNF Complexity Boolean Functions with a Simple Certificate for CNF Complexity
skos:notation
RIV/67985807:_____/12:00351382!RIV13-AV0-67985807
n14:predkladatel
n15:ico%3A67985807
n3:aktivita
n4:P n4:Z n4:I
n3:aktivity
I, P(1M0545), P(GAP202/10/1188), P(GP201/07/P168), Z(AV0Z10300504)
n3:cisloPeriodika
4-5
n3:dodaniDat
n16:2013
n3:domaciTvurceVysledku
n12:3559491
n3:druhVysledku
n6:J
n3:duvernostUdaju
n18:S
n3:entitaPredkladatele
n19:predkladatel
n3:idSjednocenehoVysledku
125381
n3:idVysledku
RIV/67985807:_____/12:00351382
n3:jazykVysledku
n9:eng
n3:klicovaSlova
Boolean functions; CNF representations
n3:klicoveSlovo
n7:Boolean%20functions n7:CNF%20representations
n3:kodStatuVydavatele
NL - Nizozemsko
n3:kontrolniKodProRIV
[607A65795562]
n3:nazevZdroje
Discrete Applied Mathematics
n3:obor
n5:BA
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
3
n3:projekt
n11:1M0545 n11:GP201%2F07%2FP168 n11:GAP202%2F10%2F1188
n3:rokUplatneniVysledku
n16:2012
n3:svazekPeriodika
160
n3:tvurceVysledku
Čepek, O. Kučera, P. Savický, Petr
n3:wos
000301211100002
n3:zamer
n17:AV0Z10300504
s:issn
0166-218X
s:numberOfPages
18
n20:doi
10.1016/j.dam.2011.05.013