arXiv · Oct 8, 2026
An ETH-based quasipolynomial lower bound for Dualization
By Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from 3SAT to the complement of Dual: Given a 3CNF formula with n variables, the reduction constructs hypergraphs H and L of total size 2^O(n^(2/3)(log n)^(1/3)) such that L subseteq Tr(H) and the formula is satisfiable if and only if L≠ Tr(H), where Tr(H) is the set of minimal transversals of H. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither Dual nor Dualization admits an algorithm running in N^o(√log N/loglog N) time, where N is the input size for Dual and the combined input and output size for Dualization. In particular, Dualization cannot be solved in output-polynomial time under ETH.