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). This problem is equivalent to decide whether two given non-redundant DNFs are dual. While it is well-known that DUAL can be decided in time n^{o(log n)), the precise complexity of this problem has been open problem for over 20 years. The "guess-and-check" complexity class GC(f(n),C) contains all problems that after a nondeterministic guess of O(f(n)) bits can be decided (checked) in complexity class C. It is known that non-DUAL, the complement of DUAL, is in GC(log^2 n, PTIME) and it was more recently shown that DUAL lies in DSPACE[log^2 n]. It was conjectured that non-DUAL is in GC(log^2 n, LOGSPACE).

In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class GC(log^2 n, TC_0) which is contained in GC(log^2 n, LOGSPACE). Wh here refer to the logtime-uniform version of TC_0, which corresponds first order logic augmented by majority quantifiers (also known as FOM). We achieve the latter bound in two steps. First we develop a new nondeterministic algorithm for DUAL that exploits, and slightly modifies, existing problem decomposition methods and uses only O(log^2 n) nondeterministic bits. We then proceed by a logical analysis, that allows us to formulate the deterministic part in FOM, i.e., in first order logic with majority quantifiers. Putting these results together yields the desired upper bound GC(log^2 n, TC_0). In summary, we have derived an improved upper bound for DUAL via logical methods.