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 O(n)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.
展开▼
机译：Golumbic等。 （Discrete Appl。Math。154：1465-1477，2006）将单调布尔函数f的可读性定义为最小整数k，从而存在一个等价于f的∧-∨公式，其中每个变量最多出现k次。他们询问是否存在多项式时间算法，该算法以CNF或DNF形式给出单调布尔函数f，检查对于固定k，f是否为read-k函数。在本文中，对于k = 2，我们已经部分地回答了这个问题，这表明确定给定的单调公式是否表示二次函数是NP难的。从我们的归纳中还可以得出，在给定的单因素布尔函数f：{0,1} n →{0,1}内近似O（n ）mathcal {O}（n）。我们还以CNF（或DNF）形式给出的单调布尔函数的可读性给出了严格的亚线性上限，该参数由CNF中的项数和每个项的最大大小或更一般地最大的变量数来参数化任意常数项的交集。如果可以对DNF的变量进行排序，以使每一项都由一组连续的变量组成，则我们会在可读性上给出更严格的对数界限。
展开▼
