On the gap between \(\mathit{ess}(f)\) and \(\mathit{cnf}_{-}\mathit{size}(f)\)
type: Item
instance of: scholarly article
title: On the gap between \(\mathit{ess}(f)\) and \(\mathit{cnf}_{-}\mathit{size}(f)\)
zbMATH Open document ID: 1260.06018
author: Lisa Hellerstein
author: Devorah Kletenik
published in: Discrete Applied Mathematics
publication date: 2012-11-22T00:00:00Z
review text: Let \(f\) be a Boolean function of \(n\) variables. The gap studied in this paper is the ratio \(\mathit{cnf}_{-}\mathit{size}(f)/\mathit{ess}(f)\), where the numerator is the minimum number of clauses in a CNF formula representing \(f\), while the denominator is the size of the largest set of false points of \(f\), no two of which falsify the same implicate of \(f\). The authors prove the existence of a function \(f\) for which the gap equals \(\Theta(n)\) and of a function \(f\) whose gap is at least \(2^{\Theta(n)}\). The case of Horn functions is studied in more detail.
reviewed by: Sergiu Rudeanu
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6109928
zbMATH Keywords: DNF
zbMATH Keywords: CNF
zbMATH Keywords: Horn function
zbMATH Keywords: formula size
MaRDI profile type: Publication
full work available at URL: j.dam.2012.07.004
OpenAlex ID: W1554694446
DOI: 10.1016/J.DAM.2012.07.004
description: scientific article; zbMATH DE number 6109928