On Generating All Minimal True and Maximal False Vectors of Monotone Boolean Functions

Let $M:\{0,1\}^n \rightarrow \{0,1\}$ be a monotone Boolean
function, and let $F$ and $T$ be the sets of all maximal false
and all minimal true vectors of $M$, respectively. We show that
for any function $M$ given by a (quasi) polynomial-time point-to-
value oracle, all elements in $F \cup T$ can be generated in
quasi-polynomial incremental time. In particular, testing the
duality of monotone disjunctive (or conjunctive) normal forms
can be done in quasi-polynomial time. On the other hand, we show
that for some classes of polynomial-time computable monotone
functions $M$, it is coNP-hard to test either of the conditions
$S=F$ of $S=T$, where $S$ is an explicitly given set of Boolean
vectors. This provides evidence that for each of these classes
neither $F$ nor $T$ can be generated in quasi-polynomial time.
Such classes of monotone functions naturally arise in convex
programming, game theory, networs and relay contact circuits,
and include a subset of $\vee, \wedge-$formulae of depth $3$.


Joint work with M. Fredman and V. Gurvich.