Monotone Boolean dualization is in co-NP[log2 n]

In 1996, Fredman and Khachiyan [J. Algorithms 21 (1996) 618-628] presented a remarkable algorithm for the problem of checking the duality of a pair of monotone Boolean expressions in disjunctive normal form. Their algorithm runs in n(o(logn)) time, thus giving evidence that the problem lies in an intermediate class between P and co-NP. In this paper we show that a modified version of their algorithm requires deterministic polynomial time plus O(log(2) n) nondeterministic guesses, thus placing the problem in the class co-NP[log(2) n]. Our nondeterministic version has also the advantage of having a simpler analysis than the deterministic one. (C) 2002 Elsevier Science B.V All rights reserved.