No Efficient Disjunction or Conjunction of Switch-Lists

1.Introduction

Switch-lists are a representation language for Boolean functions introduced in [1], strongly related to interval representations [7]. The idea is to write the values of a Boolean function f on all lexicographically ordered inputs in a value table. Then, to encode f, it suffices to remember the value of f on the first input and the inputs at which the value of f changes from that of its predecessor. The resulting data structure is called a switch-list representation of f. Clearly switch list representations can be far more succinct than truth tables, e.g. for constant functions.

To systematically understand the properties of switch-lists beyond this, Chromý and Čepek [2] analyzed them in the context of the so-called knowledge compilation map. This framework, introduced in the ground-breaking work of Darwiche and Marquis [3] gives a list of standard properties which should be analyzed for languages used in the area of knowledge compilation along different axes: succinctness, queries and transformations. The idea of the knowledge compilation map has had a huge influence and the approach of [3] is widely applied in knowledge compilation, see e.g. [4–6] for a very small sample.

Chromý and Čepek [2] analyzed switch-lists along the properties of the knowledge compilation map and got a nearly complete picture. It turns out that switch-lists, while being generally much more succinct than truth tables, have many of their good properties. In particular, all of the queries in [3] (e.g. consistency, entailement and counting) can be answered in polynomial time on switch-lists and nearly all of the transformation can be performed efficiently. The only exception is that [2] leaves open if switch-lists are closed under bounded disjunction and bounded conjunction, i.e., given two Boolean functions f1 and f2 represented by switch-lists, can one compute a switch-list representation of f1∨f2, resp. f1∧f2, in polynomial time. It is shown here that this is not the case: there are Boolean functions f1, f2 such that any switch list representation of f1∨f2 is exponentially larger than those of f1 and f2. This completes the analysis of switch-lists along the criteria of the knowledge compilation map and shows that (bounded) disjunction and conjunction are the only “bad” transformations of switch-lists, as there is no hope for a polynomial-time procedure in this case.

2.Preliminaries

Let f be a Boolean function in the n variables {x1,…,xn}. Fix an order π of {1,…,n}. Then, the assignment a:{x1,…,xn}→{0,1} can be identified with the number b(a)∈{0,…,2n−1} by identifying a with b(a):=∑i=1na(xπ(i))2i−1. This allows to write a≺a′ if and only if b(a)<b(a′). The intuition behind all this is that the assignments are written in lexicographical order with respect to π and then a≺a′ if and only if a appears before a′.

A switch of the function f with respect to π is a number b∈{1,…,2n−1} such that f(b)≠f(b−1) (note that here the identification of numbers and assignments to {x1,…,xn} depending on the order π is used). The switch-list representation of f with respect to π consist of the value f(0) and an ordered list of all switches of f with respect to π. Note that, for fixed π the switch-list representation uniquely determines f and f uniquely determines the switch-list representation.

The size of a switch-list representation is defined as n times the number of switches which corresponds roughly to the natural encoding size.11 Note that the size depends strongly on the order π.

Following Darwiche and Marquis [3], switch-lists are said to satisfy bounded disjunction (resp. bounded conjunction) if there is a polynomial-time algorithm that, given two switch-list representations of functions f1,f2, computes a switch-list representation of f1∨f2 (resp. f1∧f2). Chromý and Čepek [2] also considered the restricted version of bounded disjunction (resp. conjunction) in which one assumes that the involved functions f1,f2 depend on the same set of variables.

3.The Proof

Let n∈N be even. Consider the functions f1(x1,…,xn):=(∧i=1n∕2xi)∨(∧i=1n¬xi) and f2(x1,…,xn):=(∧i=n∕2+1nxi)∨(∧i=1n¬xi).

Proof: Only give the argument for f1 is given as that for f2 is completely analogous. Fix any order π in which the variables x1,…,xn∕2 come before those in xn∕2+1,…,xn. An assignment is a model of f1 if and only if it maps all variables to 0 or it maps x1,…,xn∕2 to 1. So all models different from 0 lie in the interval [∑j=n∕2+1n2j−1,∑j=1n2j−1]. Note that this interval lies at the end of the order of all assignments. So for these models, f1 only has one switch at the beginning of the interval. To represent f1 with a switch-list one only needs one additional switch directly after 0.  □

Proof: Let X1:={x1,…,xn∕2} and X2:={xn∕2+1,…,xn}. Fix any variable order π of X1∪X2 and let ≼ denote the lexicographical order with respect to π. The last variable of π is either in X1 or in X2. Without loss of generality, assume that it is in X2 and that the last variable in π is xn.

For every assignment a to X1, two extensions e0(a) and e1(a) to X1∪X2 are constructed as follows: on X1, the assignments e0(a) and e1(a) are both identical to a; all variables in X2∖{xn} are assigned 1 and xn is assigned 0 in e0(a) and 1 in e1(a). Let π1 be the order π restricted to X1 and let ≼1 be the order of the assignments to X1 with respect to π1. Then for two assignments ei(a1) and ej(a2) it holds that ei(a1)≺ej(a2) if and only if a1≺1a2; or a1=a2 and i<j. Note that none of the assignments of the form ei(a) is the constant 0-assignment, so ei(a) satisfies f1∨f2 if and only if it satisfies (∧i=1n∕2xi)∨(∧i=n∕2+1nxi).

Now let a1,…,a2n∕2−1 be the assignments to X1 different from constant 1-assignment given in the order ≼1. Then the resulting sequence

The main result of this paper follows directly.

Proof: For disjunction, this follows directly from Observation 1 and Proposition 1 since the outcome of any polynomial-time algorithm would in particular be of polynomial size.

For conjunction, let us define f1′=¬f1 and f2′=¬f2. Observe that a switch-list of f can be negated in constant time by simply flipping the value f(0) (keeping the same permutation of variables). Clearly f1′∧f2′=¬f1∧¬f2=¬(f1∨f2) and the lower bound for f1∨f2 from Proposition 1 is of course valid also for ¬(f1∨f2). This gives us an identical lower bound for the size of any switch list representing f1′∧f2′.  □

4.Conclusion

I was shown that switch-lists neither satisfy bounded disjunction nor bounded conjunction. This even remains true if both inputs depend on the same set of variables. This completes the analysis of switch-lists in the framework of the knowledge compilation map.

Let us remark that for practical applicability of switch-lists, this is rather bad news. Many classical approaches to practical knowledge compilation use so-called bottom-up compilation: given a conjunction of clauses, or more generally constraints, F=∧i=1mCi, one first computes representations R(Ci) of individual constraints Ci. Then one uses efficient conjunction to iteratively conjoin the R(Ci) to get a representation of F. Since conjunction of even two switch-lists is hard in general, this approach is ruled out by our results.

To better understand when switch-lists are useful, it would be interesting to find classes of functions for which small switch-list representations can be computed efficiently, either theoretically or with heuristic approaches.