New results on monotone dualization and generating hypergraph transversals.
This paper considers the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism (more precisely, in polynomial time with $O(\log^2 n)$ suitably guessed bits). This result sheds new light on the complexity of this important problem.
INTRODUCTION
# Part of the work carried out while visiting TU Wien.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for pro-t or commercial advantage and that copies
bear this notice and the full citation on the -rst page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior speci-c
permission and/or a fee.
STOC'02, May 19-21, 2002, Montreal, Quebec, Canada.
Recall that the prime CNF of a monotone Boolean function
f is the unique formula
# c#S c in conjunctive normal
form where S is the set of all prime implicates of f , i.e.,
minimal clauses c which are logical consequences of f . In
this paper, we consider the following problem:
Problem Dualization
Input: The prime CNF # of a monotone Boolean
Output: The prime CNF # of its dual
It is well known that problem Dualization is equivalent to
the Transversal Computation problem, which requests
to compute the set of all minimal transversals (i.e., minimal
hitting sets) of a given hypergraph H, in other words, the
transversal hypergraph Tr(H) of H. Actually, these problems
can be viewed as the same problem, if the clauses in
a monotone CNF # are identified with the sets of variables
they contain. Dualization is a search problem; the associated
decision problem Dual is to decide whether two
given monotone prime CNFs # and # represent a pair (f, g)
of dual Boolean functions. Analogously, the decision problem
Trans-Hyp associated with Transversal Computation
is deciding, given hypergraphs H and G, whether
Tr(H).
Dualization and several problems which are like transversal
computation known to be computationally equivalent to
Dualization (see [13]) are of interest in various areas such
as database theory (e.g., [34, 43]), machine learning and
data mining (e.g., [4, 5, 10, 18]), game theory (e.g., [22, 38,
39]), artificial intelligence (e.g., [17, 24, 25, 40]), mathematical
programming (e.g., [3]), and distributed systems (e.g.,
[16, 23]) to mention a few.
While the output CNF # can be exponential in the size of
#, it is currently not known whether # can be computed
in output-polynomial (or polynomial total) time, i.e., in time
polynomial in the combined size of # and #. Any such algorithm
for Dualization (or Transversal Computation)
would significantly advance the state of the art of many
problems in the application areas. Similarly, the complexity
of Dual and Trans-Hyp is open since more than 20 years
now (cf. [2, 13, 26, 27, 29]).
Note that Dualization is solvable in polynomial total time
on a class C of hypergraphs i# Dual is in PTIME for all pairs
Dual is known to be in co-NP and
the best currently known upper time-bound is n o(log n) [15].
Determining the complexities of Dualization and Dual,
and of equivalent problems such as the transversal problems,
is a prominent open problem. This is witnessed by the fact
that these problems are cited in a rapidly growing body of
literature and have been referenced in various survey papers
and complexity theory retrospectives, e.g. [26, 30, 36].
Given the importance of monotone dualization and equivalent
problems for many application areas, and given the
long standing failure to settle the complexity of these prob-
lems, emphasis was put on finding tractable cases of Dual
and corresponding polynomial total-time cases of Dualiza-
tion. In fact, several relevant tractable classes were found
by various authors; see e.g. [6, 7, 8, 10, 12, 13, 31, 32, 35,
37] and references therein. Moreover, classes of formulas
were identified on which Dualization is not just polynomial
total-time, but where the conjuncts of the dual formula
can be enumerated with incremental polynomial delay, i.e.,
with delay polynomial in the size of the input plus the size
of all conjuncts so far computed, or even with polynomial
delay, i.e., with delay polynomial in the input size only.
Main Goal. The main goal of this paper is to present important
new polynomial total time cases of Dualization
and, correspondingly, PTIME solvable subclasses of Dual
which significantly improve previously considered classes.
Towards this aim, we first present a new algorithm Dualize
and prove its correctness. Dualize can be regarded as a
generalization of a related algorithm proposed by Johnson,
Yannakakis, and Papadimitriou [27]. As other dualization
algorithms, Dualize reduces the original problem by self-
reduction to smaller instances. However, the subdivision
into subproblems proceeds according to a particular order
which is induced by an arbitrary fixed ordering of the vari-
ables. This, in turn, allows us to derive some bounds on
intermediate computation steps which imply that Dualize,
when applied to a variety of input classes, outputs the conjuncts
of with polynomial delay or incremental polynomial
delay. In particular, we show positive results for the following
input classes:
. Degenerate CNFs. We generalize the notion of k-degen-
erate graphs [44] to hypergraphs and define k-degener-
ate monotone CNFs resp. hypergraphs. We prove that
for any constant k, Dualize works with polynomial
delay on k-degenerate inputs. Moreover, it works in
output-polynomial time on O(log n)-degenerate CNFs.
. Read-k CNFs. A CNF is read-k, if each variable appears
at most k times in it. We show that for read-k
CNFs, problem Dualization is solvable with polynomial
delay, if k is constant, and in total polynomial
time, if O(log(#). Our result for constant k
significantly improves upon the previous best known
algorithm [10], which has a higher complexity bound,
is not polynomial delay, and outputs the clauses of
in no specific order. The result for O(log #) is
a non-trivial generalization of the result in [10], which
was posed as an open problem [9].
. Acyclic CNFs. There are several notions of hyper-graph
resp. monotone CNF acyclicity [14], where the
most general and well-known is #-acyclicity. As shown
in [13], Dualization is polynomial total time for #-
acyclic CNFs; #-acyclicity is the hereditary version of
#-acyclicity and far less general. A similar result for #-
acyclic prime CNFs was left open. We give a positive
answer and show that for #-acyclic prime #, Dualization
is solvable with polynomial delay.
. Formulas of Bounded Treewidth. The treewidth [41]
of a graph expresses its degree of cyclicity. Treewidth
is an extremely general notion, and bounded treewidth
generalizes almost all other notions of near-acyclicity.
Following [11], we define the treewidth of a hyper-graph
resp. monotone CNF # as the treewidth of its
associated (bipartite) variable-clause incidence graph.
We show that Dualization is solvable with polynomial
delay (exponential in k) if the treewidth of # is
bounded by a constant k, and in polynomial total time
if the treewidth is O(log log #).
. Recursive Applications of Dualize and k-CNFs.
We show that if Dualize is applied recursively and
the recursion depth is bounded by a constant, then
Dualization is solved in polynomial total time. We
apply this to provide a simpler proof of the known
result [6, 13] that monotone k-CNFs (where each conjunct
contains at most k variables) can be dualized in
output-polynomial time.
After deriving the above results, we turn our attention (in
Section 5) to the fundamental computational nature of problems
Dual and Trans-Hyp in terms of complexity theory.
Complexity: Limited nondeterminism. In a landmark
paper, Fredman and Khachiyan [15] proved that problem
Dual can be solved in quasi-polynomial time. More pre-
cisely, they first gave an algorithm A solving the problem in
n) time, and then a more complicated algorithm B
whose runtime is bounded by n 4#(n) where #(n) is defined
by #(n) As noted in [15], #(n) # log n/ log log
o(log n); therefore, duality checking is feasible in n o(log n)
time. This is the best upper bound for problem Dual so far,
and shows that the problem is most likely not NP-complete.
A natural question is whether Dual lies in some lower complexity
class based on other resources than just runtime. In
the present paper, we advance the complexity status of this
problem by showing that its complement is feasible with limited
nondeterminism, i.e, by a nondeterministic polynomial-time
algorithm that makes only a poly-logarithmic number
of guesses. For a survey on complexity classes with limited
nondeterminism, and for several references, see [19]. We
first show by a simple and self-contained proof that testing
non-duality is feasible in polynomial time with O(log 3 n)
nondeterministic steps. We then observe that this can be
improved to O(log 2 n) nondeterministic steps. This result is
surprising, because most researchers dealing with the complexity
of Dual and Trans-Hyp believed so far that these
problems are completely unrelated to limited nondeterminism

We believe that the results presented in this paper are signif-
icant, and we are confident they will prove useful in various
contexts. First, we hope that the various polynomial/output-
polynomial cases of the problems which we identify will lead
to better and more general methods in various application
areas (as we show, e.g. in learning and data mining [10]), and
that based on the algorithm Dualize or some future modifi-
cations, further relevant tractable classes will be identified.
Second, we hope that our discovery on limited nondeterminism
provides a new momentum to complexity research
on Dual and Trans-Hyp, and will push it towards settling
these longstanding open problems.
2. PRELIMINARIES AND NOTATION
A Boolean function (in short, function) is a mapping f :
{0, 1} n
# {0, 1}, where v # {0, 1} n is called a Boolean vector
(in short, vector). As usual, we write g # f if f and g satisfy
A function f is monotone (or positive), if
for all i) implies f(v) # f(w) for all v, w # {0, 1} n . Boolean
variables x1 , x2 , . , xn and their complements - x1 , -
x2 , . , -
xn
are called literals. A clause (resp., term) is a disjunction
(resp., conjunction) of literals containing at most one of x i
and -
x i for each variable. A clause c (resp., term t) is an
implicate (resp., implicant) of a function f , if f # c (resp.,
moreover, it is prime, if there is no implicate c # < c
no implicant t # > t) of f , and monotone, if it consists
of positive literals only. We denote by P I(f) the set of all
prime implicants of f .
A conjunctive normal form (CNF) (resp., disjunctive normal
form, DNF) is a conjunction of clauses (resp., disjunction
of terms); it is prime (resp. monotone), if all its members
are prime (resp. monotone). For any CNF (resp., DNF) #,
we denote by |#| the number of clauses (resp., terms) in it.
Furthermore, for any formula #, we denote by V (#) the set
of variables that occur in #, and by # its length, i.e., the
number of literals in it.
As well-known, a function f is monotone i# it has a monotone
CNF. Furthermore, all prime implicants and prime implicates
of a monotone f are monotone, and it has a unique
prime CNF, given by the conjunction of all its prime impli-
cates. For example, the monotone f such that
(0111), (1111)} has the unique
prime
Recall that the dual of a function f , denoted f d , is defined
by f d x is the complement of f and
respectively. By definition, we have (f d From De
Morgan's law, we obtain a formula for f d from any one of f
by exchanging # and # as well as the constants 0 and 1. For
example, if f is given by
represented by For a monotone
be the prime CNF of f d . Then
by De Morgan's law, f has the (unique) prime DNF
Thus, we will regard Dualization also as
the problem of computing the prime DNF of f from the
prime CNF of f .
3. ORDERED GENERATION OF TRANSVERSAL

In what follows, let f be a monotone function and # its
prime CNF, where we assume w.l.o.g. that all variables x j
n) appear in #. Let # i n) be the
CNF obtained from # by fixing variables x
with 1. By definition, we have
Example 3.1. Consider
Similarly, for the prime DNF
of f , we denote by # i the DNF obtained from # by fixing
variables x Clearly, we have
denoted
by f i .
Proposition 3.1. Let # and # be any CNF and DNF for
f , respectively. Then,
(a) # i # and |# i | #|, and
Denote by # i n) the CNF consisting of all the
clauses in # i but not in # i-1 .
Example 3.2. For the above example, we have
Note that #
have
denote the CNF consisting of
all the clauses c such that c contains no literal in t i-1 and
appears in # i . For example, if
It follows from (2)
that for all
Lemma 3.2. For any term t #PI (f i-1 ), let g i,t be the
function represented by # i [t]. Then |PI (g i,t )|# i | #|.
Proof. Let
Then by (3), t # s is an implicant of # i . Hence, some t s
exists such that t s
# t#s. Note that V (t)#V
#, and hence we have V
otherwise there exists a clause c in # i [t] such that V (c) #
For any s # PI (g i,t ) such that s #= s # , let t s , t s #
such that t s
# t#s and t s #
respectively. By the above
discussion, we have t s
This completes the proof.
We now describe our algorithm Dualize for generating the
set PI (f ). It is inspired by a similar graph algorithm of
Johnson, Yannakakis, and Papadimitriou [27], and can be
regarded as a generalization. Here, we say that term s is
smaller than term t if
i.e., as vector, s is lexicographically smaller than t.
Algorithm Dualize
Input: The prime CNF # of a monotone function f .
Output: The prime DNF of f , i.e. all prime implicants
of function f .
Compute the smallest prime implicant t min
of f and set Q := { t min };
Step 2:
while Q # do
begin
Remove the smallest t from Q and output t;
for each i with x do
begin
Compute the prime DNF # (t,i) of the
function represented by # i [t];
for each term t # in # (t,i) do
begin
if t i-1 # t # is a prime implicant of f i then
begin
Compute the smallest prime implicant
t # of f such that t #
Theorem 3.3. Algorithm Dualize correctly outputs all
increasing order.
Proof. (Sketch) First note that the term t # inserted in
when t is output is larger than t. Indeed, t #= 1) and
t i-1 are disjoint and V (t # {x1 ,. , x i-1}. Hence, every
term in Q is larger than all terms already output, and the
output sequence is increasing. We show by induction that,
if t is the smallest prime implicant of f that was not output
yet, then t is already in Q. This clearly proves the result.
Clearly, the above statement is true if . Assume now
that t #= t min is the smallest among the prime implicants not
output yet. Let i be the largest index such that t i is not a
prime implicant of f i . This i is well-defined, since otherwise
must hold, a contradiction. Now we have (1) i <
n and (2)
is a prime implicant of fn (= f) and (2) follows from the
maximality of i. Let s # PI (f i ) such that V
let (s). Then K # holds, and since x i+1 /
V (t), the term t # x j #K x j is a prime implicant of # i+1 [s].
There exists s # PI (f) such that s #
since s#x i+1 # PI (f i+1 ). Note that # i+1 [s] #= 0. Moreover,
since s # is smaller than t, by induction s # has already been
output. Therefore, t
been considered in the
inner for-loop of the algorithm. Since s #
is a prime implicant of f i+1 , the algorithm has added the
smallest prime implicant t # of f such that t # We
finally claim that t t. Otherwise, let k be the first index
in which t # and t di#er. Then k
contradicting the
maximality of i.
Let us consider the time complexity of algorithm Dualize.
We store Q as a binary tree, where each leaf represents a
term t and the left (resp., right) son of a node at depth
the root has depth 0, encodes x
In Step 1, we can compute t min in
O(#) time and initialize Q in O(n) time. As for Step 2, let
T (t,i) be the time required to compute the prime DNF # (t,i)
from # i [t]. By analyzing its substeps, we can see that each
iteration of Step 2 requires # x i #V (t) (T (t,i)
time; note that t # is the smallest prime implicant of the
function obtained from f by fixing x
and 0 if x Thus, we have
Theorem 3.4. The output delay of Algorithm Dualize
is bounded by
t#PI (f)
time, and Dualize needs in total time
t#PI (f)
If the T (t,i) are bounded by a polynomial in the input length,
then Dualize becomes a polynomial delay algorithm, since
holds for all t # PI (f) and x
the other hand, if they are bounded by a polynomial in
the combined input and output length, then Dualize is a
polynomial total time algorithm, where |# (t,i) | #| holds
from Lemma 3.2. Using results from [2], we can construct
from Dualize an incremental polynomial time algorithm
for Dualization, which however might not output PI (f)
in increasing order. Summarizing, we have the following
corollary.
Corollary 3.5. Let
is bounded by
(i) a polynomial in n and #, then algorithm Dualize is
an O(n#T ) polynomial delay algorithm;
(ii) a polynomial in n, #, and #, then algorithm Dualize
is an O(n| |(T + | |#)) polynomial total time
algorithm; moreover, Dualization is solvable in incremental
polynomial time.
In the next section, we identify su#cient conditions for the
boundedness of T and fruitfully apply them to solve open
problems and improve previous results.
4. POLYNOMIAL CLASSES
4.1 Degenerate CNFs
We first consider the case of small # i [t]. Generalizing a
notion for graphs (i.e., monotone 2-CNFs) [44], we call a
monotone CNF # k-degenerate, if there exists a variable
ordering x1 , . , xn in which |# i
| # k for all
We call a variable ordering x1 , . , xn smallest last as in [44],
if x i is chosen in the order
|
is smallest for all variables that were not chosen. Clearly,
a smallest last ordering gives the least k such that # is k-
degenerate. Therefore, we can check for every integer k # 1
whether # is k-degenerate in O(#) time. If this holds,
then we have |# (t,i) | # n k and T
apply the distributive law
to # i [t] and remove terms t where some x j # V (t) has no
}). Thus Theorem 3.4
implies the following.
Theorem 4.1. For k-degenerate CNFs #, Dualization
is solvable with O(#n k+1 ) polynomial delay if k # 1 is
constant.
Applying the result of [33] that any monotone CNF which
has O(log n) many clauses is dualizable in incremental polynomial
time, we obtain a polynomiality result also for non-constant
degeneracy:
Theorem 4.2. For O(log #)-degenerate CNFs #, problem
Dualization is polynomial total time.
In the following, we discuss several natural subclasses of
degenerate CNFs.
4.1.1 Read-bounded CNFs
A monotone CNF # is called read-k, if each variable appears
in # at most k times. Clearly, read-k CNFs are k-degenerate,
and in fact # is read-k i# it is k-degenerate under every
variable ordering. By applying Theorems 4.1 and 4.2, we
obtain the following result.
Corollary 4.3. For read-k CNFs #, problem Dualization
is solvable
(i) with O(#n k+1 ) polynomial delay, if k is constant;
(ii) in polynomial total time, if
Note that Corollary 4.3 (i) trivially implies that Dualization
is solvable in O(|#|n k+2 ) time for constant k, since
# kn. This improves upon the previous best known algorithm
[10], which is only O(|#|n k+3 ) time, not polynomial
delay, and outputs PI (f) in no specific order. Corollary 4.3
(ii) is a non-trivial generalization of the result in [10], which
was posed as an open problem [9].
4.1.2 Acyclic CNFs
Like in graphs, acyclicity is appealing in hypergraphs resp.
monotone CNFs from a theoretical as well as a practical
point of view. However, there are many notions of acyclicity
for hypergraphs (cf. [14]), since di#erent generalizations
from graphs are possible. We refer to #-, and Berge-
acyclicity as stated in [14], for which the following proper
inclusion hierarchy is known:
Berge-acyclic #-acyclic #-acyclic #-acyclic.
The notion of #-acyclicity came up in relational database
theory. A monotone CNF # is #-acyclic reducible
by the GYO-reduction [21, 45], i.e., repeated application
of one of the two rules:
(1) If variable x i occurs in only one clause c, remove x i from
clause c.
(2) If distinct clauses c and c # satisfy
clause c from #.
to 0 (i.e., the empty clause). Note that #-acyclicity of a
monotone CNF # can be checked, and a suitable GYO-
reduction output, in O(#) time [42]. A monotone CNF
# is #-acyclic i# every CNF consisting of clauses in # is #-
acyclic. As shown in [13], the prime implicants of a monotone
f represented by a #-acyclic CNF # can be enumerated
(and thus Dualization solved) in p(#| time, where p is
a polynomial in #. However, the time complexity of Dualization
for the more general #-acyclic prime CNFs was
left as an open problem. We now show that it is solvable
with polynomial delay.
Let #= 1 be a prime CNF. Let a = a1 , a2 , . , aq be a GYO-
reduction for #, where a the #-th operation removes
x i from c, and a removes c from #. Consider the
unique variable ordering b1 , b2 , . , bn such b i occurs after b j
in a, for all i < j.
Example 4.1. Let
x3
since it has the GYO-reduction
. From this sequence, we obtain the
variable ordering
As easily checked, this ordering shows that #
is 1-degenerate. Under this ordering, we have #
That # is 1-degenerate in this example is not accidental.
Lemma 4.4. Every #-acyclic prime CNF is 1-degenerate.
Note that the converse is not true. Lemma 4.4 and Theorem
4.1 imply the following result.
Corollary 4.5. For #-acyclic CNFs #, problem Dualization
is solvable with O(#n 2 ) delay.
Observe that for a prime #-acyclic #, we have |# n. Thus,
if we slightly modify algorithm Dualize to check #
in advance (which can be done in linear time in a preprocessing
phase) such that such # i need not be considered in
step 2, then the resulting algorithm has O(n|#) delay.
Observe that the algorithm in [13] solves, minorly adapted
for enumerative output, Dualization for #-acyclic CNFs
with O(n|#) delay. Thus, the above modification of
Dualize is of the same order.
4.1.3 CNFs with bounded treewidth
A tree decomposition (of type I) of a monotone CNF # is a
tree T =(W,E) where each node w#W is labeled with a set
X(w)#V (#) under the following conditions:
1. # w#W
2. for every clause c in #, there exists some w # W such
that V (c) # X(w); and
3. for any variable x
X(w)} induce a (connected) subtree of T .
The width of T is maxw#W |X(w)| - 1, and the treewidth of
#, denoted by Tw 1 (#), is the minimum width over all its
tree decompositions.
Note that the usual definition of treewidth for a graph [41]
results in the case where # is a 2-CNF. Similarly to acyclic-
ity, there are several notions of treewidth for hypergraphs
resp. monotone CNFs. For example, tree decomposition of
type II of CNF # c#C c is defined as type-I tree decomposition
of its incident 2-CNF (i.e., graph) G(#) [11, 20].
That is, for each clause c #, we introduce a new variable
yc and construct
denote the type-II treewidth of #.
Proposition 4.6. For every monotone CNF #, it holds
that Tw 2
Proof. Let be any tree decomposition
of # having width Tw 1 (#). Introduce for all
c # new variables y c , and add y c to every X(w) such that
Clearly, the result is a type-I tree decomposition
of G(#), and thus a type-II tree decomposition of
#. Since at most 2 |X(w)| many yc are added to X(w) and
for every w # W , the result follows.
This means that if Tw 1 (#) is bounded by some constant,
then so is Tw 2 (#). Moreover, Tw 1 implies that
# is a k-CNF; we discuss k-CNFs in Section 4.2 and only
consider Tw 2 (#) here. We note that, as shown in the full
paper, there is a family of prime CNFs # which have Tw 2 (#)
bounded by constant k but are not k-CNF for any k < n
not read-k for any k < n - 1), and a family of prime
CNFs which are k-CNFs for constant k (resp., #-acyclic)
but Tw 2 (#) is not bounded by any constant.
As we show now, bounded-treewidth implies bounded degeneracy

Lemma 4.7. Let # be any monotone CNF with Tw 2
k. Then # is 2 k -degenerate.
Proof. (Sketch) Let E) with show
From this, we reversely construct a variable
ordering , an on (#) such that |# i
for all i.
Choose any leaf w # of T , and let p(w # ) be a node
in W adjacent to w # . If X(w # ) \ X(p(w # {yc | c #},
then remove w # from T . On the other hand, if
only
for
We complete a by
repeating this process, and claim it shows that |# i
for all i. Let w # be chosen during this process, and assume
that a i # X(w # ) \ X(p(w # )). Then, for each clause c # i
we must have either yc # X(w # ) or V (c) # X(w # ). Let
| #
Corollary 4.8. For CNFs # with Tw 2 (# k, Dualization
is solvable
(i) with O(#n 2 k +1 ) polynomial delay, if k is constant;
(ii) in polynomial total time, if
4.2 Recursive application of algorithm Dual-
ize
Algorithm Dualize computes in step 2 the prime DNF # (t,i)
of the function represented by # i [t]. Since #[t] is the prime
CNF of some monotone function, we can recursively apply
Dualize to # i [t] for computing # (t,i) . Let us call this variant
R-Dualize. Then we have the following result.
Theorem 4.9. If its recursion depth is d, R-Dualize
solves Dualization in O(n d-1
|#| d-1
#) time.
Proof. If min and every
# 1. This means that PI (f)={tmin} and # is a 1-CNF
(i.e., each clause in # contains exactly one variable). Thus
in this case, R-Dualize needs O(n) time. Recall that algorithm
Dualize needs, by (5), time
|# (t,i) |O(#)). If
Therefore, R-Dualize needs time O(n|#). For d # 3,
Corollary 3.5.(ii) implies that algorithm R-Dualize needs
time O(n d-1
|#| d-1
#).
Recall that a CNF # is called k-CNF if each clause in # has
at most k literals. Clearly, if we apply algorithm R-Dualize
to a monotone k-CNF #, the recursion depth of R-Dualize
is at most k. Thus we obtain the following result; it re-
establishes, with di#erent means, the main positive result of
[6, 13].
Corollary 4.10. Algorithm R-Dualize solves Dualization
in time O(n k-1
|#| k-1
#), i.e., in polynomial total
time for monotone k-CNFs # where k is constant.
5. LIMITED NONDETERMINISM
In the previous section, we have discussed polynomial cases
of monotone dualization. In this section, we now turn to
the issue of the precise complexity of this problem. For this
purpose, we consider the decision problem Dual instead of
the search problem Dualization. It appears that problem
Dual can be solved with limited nondeterminism, i.e.,
with poly-log many guessed bits by a polynomial-time non-deterministic
Turing machine. This result might bring new
insight towards settling the complexity of the problem.
We adopt Kintala and Fischer's terminology [28] and write
g(n)-P for the class of sets accepted by a nondeterministic
Turing machine in polynomial time making at most g(n)
nondeterministic steps on every input of length n. For every
n)-P. The #P
Hierarchy consists of the classes
and lies between P and NP. The #kP classes appear to
be rather robust; they are closed under polynomial time
and logspace many-one reductions and have complete problems
(cf. [19]). The complement class of #kP is denoted by
co-#kP.
We start by recalling algorithm A of [15], reformulated for
CNFs. In what follows, we view CNFs # also as sets of
clauses, and clauses as sets of literals.
Algorithm A. (reformulated for CNFs)
Input: Monotone CNFs #, representing monotone
f , g s.t. V (c)#V (c #, for all c#, c # .
Output: yes if vector w of form
Delete all redundant (i.e., non-minimal)
implicates from # and #.
Step 2:
Check that V
If any of these conditions fails, f #= g d and a
witness w is found in polynomial time (cf. [15]).
Step 3:
If |# 1, test duality in O(1) time.
Step 4:
If |# 2, find a variable x i that occurs in # or #
(w.l.o.g. in #) with frequency # 1/ log(|#|).
Let
Call algorithm A on the two pairs of forms:
If both calls return yes, then return yes (as
otherwise we obtain w such that f(w) #= g d (w) in
polynomial time (cf. [15]).
be the original input for A. For any pair (#) of
CNFs, define its volume by
|. As shown in [15], step 4 of algorithm
A divides the current (sub)problem of volume
self-reduction into subproblems (A.1) and (A.2) of respective
volumes (assuming that x i frequently occurs in #):
(#) be the recursion tree generated by A on
input (#), i.e., the root is labeled with (#). Any node a
labeled with (#) is a leaf, if A stops on input (#) during
steps 1-3; otherwise, a has a left child a l and a right child
ar corresponding to (A.1) and (A.2), i.e., labeled (#1 , #0 #
#1 ) and (#1 , #0 #1 ) respectively. That is, a l is the "high
frequency move" by the splitting variable.
We observe that every node a in T is determined by a unique
path from the root to a in T and thus by a unique sequence
seq(a) of right or left moves starting from the root of T and
ending at a. The following key lemma bounds the number
of moves of each type for certain inputs.
Lemma 5.1. Suppose |# i
|. Then for any
node a in T , seq(a) contains # v right and # log 2 v left
moves, where
|.
Proof. By (6) and (7), each move decreases the volume v
of a node label. Thus, the length of seq(a), and in particular
the number of right moves, is bounded by v. To obtain the
better bound for the left moves, we will use the following
well-known inequality:
# 1/e, for m # 1. (8)
In fact, the sequence (1 -1/x i
monotonically converges to 1/e from below. By inequality
(6), the volume va of the label of any node a such that seq(a)
contains log 2 v left moves is bounded as follows:
log n) log 2 v .
Because
| - |# i
and because of (8)
it follows that:
log v
Thus, a must be a leaf in T . Hence for every a in T , seq(a)
contains at most log 2 v left moves.
Theorem 5.2. Problem Dual is in co-#3P.
Proof. (Sketch) Instances such that either c # c #
for some c # i and c # i , the sequence seq(a) is empty,
or |# i
| > |# i
| are easily solved in deterministic
polynomial time. In the remaining cases, if f #= g d , then
there exists a leaf a in T labeled by a non-dual pair (# ).
If seq(a) is known, we can compute, by simulating A on
the branch described by seq(a), the entire path from the
root to a with all labels check that
non-dual in steps 2 and 3 of A in polynomial time.
We observe that, as noted in [15], the binary length of any
standard encoding of the input # i , # i is polynomially related
to |# i
| if algorithm A reaches step 3. Thus, to
prove the theorem, it is su#cient to show that seq(a) is obtainable
in polynomial time from O(log 3 v) suitably guessed
bits, where
|. To see this, let us represent every
seq(a) as a sequence seq #
#0 is the number of leading right moves and # i is the number
of consecutive right moves after the i-th left move in
seq(a), for
then seq # (a) = [2, 3, 0]. By Lemma 5.1, seq # (a) has length
at most log 2 v + 1. Thus, seq # (a) occupies only O(log 3 v)
bits in binary; moreover, seq(a) is trivially computed from
seq # (a) in polynomial time.
Remark 5.1. It also follows that if f #= g d , a witness
w can be found in polynomial time within O(log 3 n) nondeterministic
steps. In fact, the sequence seq(a) to a "failing
labeled (# ) describes a choice of values for all variables
in V (#) \ V (# ). By completing it with values
for show non-duality of (# ), we obtain
in polynomial time a vector w such that f(w) #= g d (w).
The aim of the above proof was to show with very simple
means that duality can be polynomially checked with limited
nondeterminism. With a more involved proof, applied to
the algorithm B of [15] (which runs in n 4#(n)+O(1) and thus
time), we can prove the following sharper result.
Theorem 5.3. Deciding if monotone CNFs # and # are
non-dual is feasible in polynomial time with O(#(n) log n)
nondeterministic steps. Thus, problem Dual is in co-#2P.
While our independently developed methods are di#erent
from those in [1], the previous result may also be obtained
from Beigel and Fu's Theorem 11 in [1]. They show how
to convert certain recursive algorithms that use disjunctive
self-reductions and have runtime bounded by f(n) into polynomial
algorithms using log f(n) nondeterministic steps (cf.
[1, Chapter 5]). However, this yields a somewhat more complicated
nondeterministic algorithm. In the full paper, we
also prove that algorithm B qualifies for this.
6.

ACKNOWLEDGMENTS

This work was supported in part by the Austrian Science
Fund project Z29-INF, by TU Wien through a scientific
collaboration grant, and by the Scientific Grant in
Aid of the Ministry of Education, Science, Sports and Culture
of Japan. We would like to thank the reviewers for their
constructive comments on this paper.
7.



--R

Molecular computing
Complexity of identification and dualization of positive Boolean functions.
On generating all minimal integer solutions for a monotone system of linear inequalities.

On the complexity of generating maximal frequent and minimal infrequent sets.
Dual subimplicants of positive Boolean functions.
time recognition of 2-monotonic positive Boolean functions given by an oracle
Dualization of regular Boolean functions.
Private communication.

Conjunctive query containment revisited.
Exact transversal hypergraphs and application to Boolean
Identifying the minimal transversals of a hypergraph and related problems.
Degrees of acyclicity for hypergraphs and relational database schemes.
On the complexity of dualization of monotone disjunctive normal forms.
How to assign votes in a distributed system.
Incremental recompilation of knowledge.
Data mining
Limited nondeterminism.
Hypertree decompositions and tractable queries.
On the universal relation.

A theory of coteries: Mutual exclusion in distributed systems.

Translating between Horn representations and their characteristic models.
"G. Stampacchia"
On generating all maximal independent sets.
Refining nondeterminism in relativized polynomial-time bounded computations
Generating all maximal independent sets: NP-hardness and polynomial-time algorithms
Combinatorial optimization: Some problems and trends.
The maximum latency and identification of positive Boolean functions.
A fast and simple algorithm for identifying 2-monotonic positive Boolean functions


Generating all maximal independent sets of bounded-degree hypergraphs
A retrospective
An O(nm)-time algorithm for computing the dual of a regular Boolean function
Coherent Structures and Simple Games.
Every one a winner
A theory of diagnosis from first principles.
Graph minors II: Algorithmic aspects of tree-width
Simple linear time algorithms to test chordality of graphs
Minimal keys and antikeys.
Colouring, stable sets and perfect graphs.
An algorithm for tree-query membership of a distributed query
--TR
Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs
How to assign votes in a distributed system
Design by exmple: An application of Armstrong relations
The minimal keys and antikeys
A theory of diagnosis from first principles
Dualization of regular Boolean functions
On generating all maximal independent sets
An O(<italic>nm</italic>)-time algorithm for computing the dual of a regular Boolean function
Exact transversal hypergraphs and application to Boolean MYAMPERSANDmgr;-functions
Identifying the Minimal Transversals of a Hypergraph and Related Problems
Complexity of identification and dualization of positive Boolean functions
Colouring, stable sets and perfect graphs
Limited nondeterminism
On the complexity of dualization of monotone disjunctive normal forms
Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
Data mining, hypergraph transversals, and machine learning (extended abstract)
The Maximum Latency and Identification of Positive Boolean Functions
Generating all maximal independent sets of bounded-degree hypergraphs
A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
Hypertree decompositions and tractable queries
Degrees of acyclicity for hypergraphs and relational database schemes
Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries
Dual-Bounded Generating Problems
A Theory of Coteries
Conjunctive Query Containment Revisited
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
NP-Completeness
On Horn Envelopes and Hypergraph Transversals
On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets

--CTR
Dimitris J. Kavvadias , Elias C. Stavropoulos, Monotone boolean dualization is in co-NP[log2n], Information Processing Letters, v.85 n.1, p.1-6, January
Thomas Eiter , Kazuhisa Makino, On computing all abductive explanations, Eighteenth national conference on Artificial intelligence, p.62-67, July 28-August 01, 2002, Edmonton, Alberta, Canada
Georg Gottlob , Reinhard Pichler , Fang Wei, Tractable database design through bounded treewidth, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Leonid Khachiyan , Endre Boros , Khaled Elbassioni , Vladimir Gurvich, A global parallel algorithm for the hypergraph transversal problem, Information Processing Letters, v.101 n.4, p.148-155, February, 2007
Peter L. Hammer , Alexander Kogan , Bruno Simeone , Sndor Szedmk, Pareto-optimal patterns in logical analysis of data, Discrete Applied Mathematics, v.144 n.1-2, p.79-102, November 2004
hypergraph acyclicity;dualization;treewidth;limited nondeterminism;output-polynomial algorithms;transversal computation;combinatorial enumeration