Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic

The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide whether $\mathcal{H}$ consists precisely of all minimal transversals of $\mathcal{G}$ (in which case we say that $\mathcal{G}$ is the dual of $\mathcal{H}$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $\mathrm{G}\mathrm{C}({\log }^{2}n,\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E})$, where $\mathrm{G}\mathrm{C}(f(n),\mathcal{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 $\mathcal{C}$. It was conjectured that non-DUAL is in $$\mathrm{G}\mathrm{C}$(\log^2 n,$\mathrm{L}\mathrm{O}\mathrm{G}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$)$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $$\mathrm{G}\mathrm{C}$(\log^2 n,$\mathrm{T}\mathrm{C}$^0)$whichisasubclassof$$\mathrm{G}\mathrm{C}$(\log^2 n,$\mathrm{L}\mathrm{O}\mathrm{G}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$)$\mathrm{.}Wehererefertothelogtime-uniformversionof$$\mathrm{T}\mathrm{C}$^0$,whichcorrespondsto$$\mathrm{F}\mathrm{O}(\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T})$$, 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 non-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 $\mathrm{F}\mathrm{O}(\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T})$. From this result, by the well known inclusion ${\mathrm{T}\mathrm{C}}^0\subseteq \mathrm{L}\mathrm{O}\mathrm{G}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, it follows that DUAL belongs also to $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}[{\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 $\mathcal{G}$ and $\mathcal{H}$, computes in quadratic logspace a transversal of $\mathcal{G}$ missing in $\mathcal{H}$.