About: Boolean Functions with a Simple Certificate for CNF Complexity

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Boolean Functions with a Simple Certificate for CNF Complexity Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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. (en)
Title	Boolean Functions with a Simple Certificate for CNF Complexity Boolean Functions with a Simple Certificate for CNF Complexity (en)
skos:prefLabel	Boolean Functions with a Simple Certificate for CNF Complexity Boolean Functions with a Simple Certificate for CNF Complexity (en)
skos:notation	RIV/67985807:_____/12:00351382!RIV13-AV0-67985807
http://linked.open...avai/riv/aktivita	I P Z
http://linked.open...avai/riv/aktivity	I, P(1M0545), P(GAP202/10/1188), P(GP201/07/P168), Z(AV0Z10300504)
http://linked.open...iv/cisloPeriodika	4-5
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Savický, Petr
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Ústav informatiky AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	125381
http://linked.open...ai/riv/idVysledku	RIV/67985807:_____/12:00351382
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Boolean functions; CNF representations (en)
http://linked.open.../riv/klicoveSlovo	Boolean functions CNF representations
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[607A65795562]
http://linked.open...i/riv/nazevZdroje	Discrete Applied Mathematics
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science KnowSched: Knowledge Techniques in Scheduling Boolean functions
http://linked.open...UplatneniVysledku	2012
http://linked.open...v/svazekPeriodika	160
http://linked.open...iv/tvurceVysledku	Kučera, P. Savický, Petr Čepek, O.
http://linked.open...ain/vavai/riv/wos	000301211100002
http://linked.open...n/vavai/riv/zamer	Informatika pro informační společnost: modely, algoritmy, aplikace
issn	0166-218X
number of pages	18 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.dam.2011.05.013

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software