Boolean functions with a simple certificate for CNF complexity

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/67985807:_____/12:00351382

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Boolean functions with a simple certificate for CNF complexity

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Boolean functions with a simple certificate for CNF complexity

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

160

Číslo periodika v rámci svazku

4-5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

365-382

Kód UT WoS článku

000301211100002

EID výsledku v databázi Scopus

—