Achieving new upper bounds for the hypergraph duality problem through logic

Abstract

The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs G and H, decide whether H consists precisely of all minimal transversals of G (in which case we say that G is the dual of H, or, equivalently, the transversal hypergraph of H). This problem is equivalent to deciding whether two given non-redundant monotone DNFs/CNFs are dual. It is known that co-DUAL, the complementary problem to DUAL, is in GC(log^2 n, PTIME), where GC(f(n), C) denotes the complexity class of all problems that after a nondeterministic guess of O(f(n)) bits can be decided (checked) within complexity class C. It was conjectured that co-DUAL is in GC(log^2 n, LOGSPACE). In this paper we prove this conjecture and actually place the co-DUAL problem into the complexity class GC(log^2 n, TC^0) which is a subclass of GC(log^2 n, LOGSPACE). We here refer to the logtime-uniform version of TC^0, which corresponds to FO(COUNT), i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for co-DUAL that requires to guess O(log^2 n) bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in FO(COUNT). From this result, by the well known inclusion TC^0 \subseteq LOGSPACE, it follows that DUAL belongs also to DSPACE[log^2 n]. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs G and H, computes in quadratic logspace a transversal of G missing in H.