Exponential time limits found for dualizing monotone Boolean functions
An ETH-based quasipolynomial lower bound for Dualization
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The paper studies a hard problem in computer science about finding certain minimal sets related to logical formulas or networks. The best algorithms so far take quasipolynomial time, which is slower than polynomial but faster than exponential. The authors show that, assuming a common complexity assumption called the Exponential Time Hypothesis, no significantly faster algorithm can exist. This means the problem is unlikely to be solved efficiently in general, helping explain why finding quick solutions has been so challenging.
What this means in practice
- •For algorithm designers: Avoid efforts to design output-polynomial time algorithms for dualization tasks, saving development time.
- •For complexity theorists: Use the reduction and lower bound to guide complexity classifications for related Boolean function problems.
A theory result. No direct application yet.
Authors
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Abstract
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 \textsc{3SAT} to the complement of \textsc{Dual}: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $\mathcal H$ and $\mathcal L$ of total size $2^{\bigoh(n^{2/3}(\log n)^{1/3})}$ such that $\mathcal L \subseteq \Tr(\mathcal H)$ and the formula is satisfiable if and only if $\mathcal L\neq \Tr(\mathcal H)$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither \textsc{Dual} nor \textsc{Dualization} admits an algorithm running in $N^{o(\sqrt{\log N/\log\log N})}$ time, where $N$ is the input size for \textsc{Dual} and the combined input and output size for \textsc{Dualization}. In particular, \textsc{Dualization} cannot be solved in output-polynomial time under ETH.