Complexity of Identification and Dualization of Positive Boolean Functions

AbstractWe consider in this paper the problem of identifying min T(ƒ) and max F(ƒ) of a positive (i.e., monotone) Boolean function ƒ, by using membership queries only, where min T(ƒ) (max F(ƒ)) denotes the set of minimal true vectors (maximal false vectors) of ƒ. It is shown that the existence of an incrementally polynomial algorithm for this problem is equivalent to the existence of the following algorithms, where ƒ and g are positive Boolean functions: •An incrementally polynomial algorithm to dualize ƒ;•An incrementally polynomial algorithm to self-dualize ƒ;•A polynomial algorithm to decide if ƒ and are mutually dual;•A polynomial algorithm to decide if ƒ is self-dual;•A polynomial algorithm to decide if ƒ is saturated;•A polynomial algorithm in |min (ƒ)| + |max (ƒ)| to identify min (ƒ) only. Some of these are already well known open problems in the respective fields. Other related topics, including various equivalent problems encountered in hypergraph theory and theory of coteries (used in distributed systems), are also discussed