PaperfootJoin free
arXiv

Proof sets a conditional speed limit for a set-listing problem

Under a hypothesis about logic problems, the proof ruled out a running time bounded by any fixed power of the combined input and output size.

Paper by Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

The paper proved a conditional speed limit for Dualization, the problem of listing every minimal set that touches each group in a collection. Here, minimal means that removing any member would leave at least one group untouched.

The result depended on the Exponential Time Hypothesis. This says that, in the worst case, solving a standard kind of logic formula requires time growing exponentially with its number of variables. The authors linked that logic problem to checking whether a list contains all the minimal sets. Under the hypothesis, no algorithm could always produce the complete list in time bounded by any fixed power of the combined input and output size.

Why it matters

The proof gave a conditional negative answer to a long-standing question: whether the time needed for this listing problem can stay within a fixed power of the information read and produced.

Caveats

The limit depends on the Exponential Time Hypothesis being true; it is not an unconditional impossibility result or a measurement of practical running times. The paper is a preprint, not yet peer-reviewed.

In this paper

complexity of Dual and Dualization

Methods
GPT-6 Astra

What it shows

Assuming the Exponential Time Hypothesis, neither Dual nor Dualization admits an algorithm running in N^o(√log N/loglog N) time.

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.

Abstract

Under the Exponential Time Hypothesis, Dualization cannot be solved in output-polynomial time.

In particular, Dualization cannot be solved in output-polynomial time under ETH.

Abstract

Assuming ETH, Minimal Dominating Set Enumeration on co-bipartite graphs has no algorithm running in N^o(√log N/loglog N) time.

where N=\lVert G\rVert+\lVert\operatorname{MD}(G)\rVert is the combined size of the input graph G and the output, even when G is restricted to co-bipartite graphs.

Corollary 11.

CoNP-hardness of Dual under polynomial-time many-one reductions would imply NP is contained in QP.

Indeed, coNP-hardness of Dual under polynomial-time many-one reductions would imply \mathrm{NP}\subseteq\mathrm{QP}, where \mathrm{QP} denotes deterministic quasipolynomial time.

3 Discussion

The results rule out output-polynomial-time enumeration under ETH for every graph class containing all co-bipartite graphs, including perfect graphs.

Consequently, the presented results rule out output-polynomial-time enumeration under ETH for every graph class containing all co-bipartite graphs, including perfect graphs.

3 Discussion

Quoted word for word from the full text on arXiv.

The paper

An ETH-based quasipolynomial lower bound for Dualization

Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa

arXiv, Oct 8, 2026, Open access, CC BY, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.11473

arXiv:2610.11473v2 in cs.DS, also cs.DM

AbstractPDFHTML

Cite as BibTeX
@misc{kobayashi2026ethbased,
  title = {An ETH-based quasipolynomial lower bound for Dualization},
  author = {Kobayashi, Yasuaki and Kurita, Kazuhiro and Wasa, Kunihiro},
  year = {2026},
  eprint = {2610.11473},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arxiv.2610.11473},
  url = {https://arxiv.org/abs/2610.11473}
}

Related