On the readability of monotone Boolean formulae

Khaled Elbassioni (), Kazuhisa Makino () and Imran Rauf ()
Additional contact information
Khaled Elbassioni: Max-Planck-Institut für Informatik
Kazuhisa Makino: University of Tokyo
Imran Rauf: Max-Planck-Institut für Informatik

Journal of Combinatorial Optimization, 2011, vol. 22, issue 3, No 1, 293-304

Abstract: Abstract Golumbic et al. (Discrete Appl. Math. 154:1465–1477, 2006) defined the readability of a monotone Boolean function f to be the minimum integer k such that there exists an ∧−∨-formula equivalent to f in which each variable appears at most k times. They asked whether there exists a polynomial-time algorithm, which given a monotone Boolean function f, in CNF or DNF form, checks whether f is a read-k function, for a fixed k. In this paper, we partially answer this question already for k=2 by showing that it is NP-hard to decide if a given monotone formula represents a read-twice function. It follows also from our reduction that it is NP-hard to approximate the readability of a given monotone Boolean function f:{0,1} n →{0,1} within a factor of $\mathcal{O}(n)$ . We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form, parameterized by the number of terms in the CNF and the maximum size in each term, or more generally the maximum number of variables in the intersection of any constant number of terms. When the variables of the DNF can be ordered so that each term consists of a set of consecutive variables, we give much tighter logarithmic bounds on the readability.

Keywords: Read-once functions; Monotone Boolean functions; Readability; Complexity of monotone Boolean functions (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9283-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:3:d:10.1007_s10878-009-9283-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9283-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().