Abstract
Boolean function f on n variables is represented by set A of disjoint intervals of n-bit integers if there exists an order P of the variables of f such that the following condition holds: a truth assignment x of zero-one values to variables of f is a truepoint of f if and only if x viewed as an integer using the prescribed order P of bits belongs to an interval in A. The recognition problem was studied for the case when A consists of a single interval.
It was shown to be co-NP hard if no additional requirements are placed on the input DNF. On the other hand, for several special classes of DNFs a polynomial time algorithm was derived which decides whether the input DNF represents a 1-interval function, and in the affirmative case outputs the order P and two integers [a,b]bounding the interval.
In this paper we address the case when A consists of two disjoint intervals. We present a polynomial-time recognition algorithm which works for positive and negative DNFs.