---
id: "2026-10-08-dualization-eth-lower-bound-gpt-6-astra"
url: "https://postcutoff.com/e/2026-10-08-dualization-eth-lower-bound-gpt-6-astra/"
as_of: "2026-10-09T19:24:00+02:00"
date: "2026-10-08"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Preprint only
sources: 1
editor: Adam Bicz
human_review: null
version: null
---

As of: 2026-10-09 19:24 CEST.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code). Human editor: Adam Bicz.
Canonical page: https://postcutoff.com/e/2026-10-08-dualization-eth-lower-bound-gpt-6-astra/

# GPT-6 Astra finds a 3SAT reduction showing monotone Dualization (minimal hypergraph transversals) has no polynomial algorithm under ETH

On 8 Oct 2026 Yasuaki Kobayashi, Kazuhiro Kurita and Kunihiro Wasa posted arXiv 2610.11473: a deterministic reduction from 3SAT with n variables to the complement of Dual, producing hypergraphs of size 2^O(n^(2/3) (log n)^(1/3)). Under the Exponential Time Hypothesis, neither Dual nor Dualization has an N^o(√(log N / log log N)) algorithm, so Dualization has no output-polynomial algorithm. The best known algorithm, Fredman–Khachiyan (1996), runs in quasipolynomial time N^O(log N / log log N). Disclosure: "The proof of Theorem 1 was originally discovered by GPT-6 Astra (OpenAI). The authors subsequently reconstructed and revised the argument and rewrote its exposition."

## Key facts
- Problem: Dual asks whether two monotone CNFs are mutually dual (equivalently whether L = Tr(H) for hypergraphs H, L); Dualization asks to enumerate all minimal transversals of H. Their output-polynomial solvability is a long-standing open problem; Fredman–Khachiyan's 1996 algorithm runs in N^O(log N / log log N)
- Theorem 1: a deterministic algorithm maps a 3CNF with n variables to hypergraphs H, L with L ⊆ Tr(H), of size 2^O(n^(2/3)(log n)^(1/3)), such that the formula is satisfiable iff L ≠ Tr(H)
- Consequence under ETH: no N^o(√(log N / log log N)) algorithm for Dual or Dualization, hence no polynomial-time algorithm for Dual and no output-polynomial enumeration for Dualization. It also rules out output-polynomial algorithms for the many problems known to be Dualization-hard (minimal dominating sets, which are 'polynomially equivalent', and others)
- AI disclosure (verbatim): 'The proof of Theorem 1 was originally discovered by GPT-6 Astra (OpenAI). The authors subsequently reconstructed and revised the argument and rewrote its exposition. The same AI model was also used to prepare drafts of several parts of the manuscript. The authors have verified the correctness of the results and take full responsibility'
- The paper is short (main text ends on page 9); unrefereed; no Lean formalization; no expert reactions found on X, HN or blogs as of 9 Oct
- Not in OpenAI's 6 Oct catalogue (no Dualization or transversal family in CONTENTS.md)

## What happened

Dualization of monotone Boolean functions appears in databases, data mining, AI and convex geometry, and many enumeration
problems are known to be exactly as hard. Fredman and Khachiyan showed in 1996 that it can be done in quasipolynomial time,
and since then the question has been whether it can be done in output-polynomial time. Most work has found tractable
special cases.

Kobayashi, Kurita and Wasa give a subexponential reduction from 3SAT: partial assignments to blocks of variables become
vertices, and the formula is satisfiable exactly when a candidate list of minimal transversals is incomplete. With the
Exponential Time Hypothesis this rules out polynomial-time duality testing. The authors say GPT-6 Astra discovered the
proof of the main theorem.

## Why it matters

If it holds, it closes the main question about Dualization conditionally. The quasipolynomial algorithm is close to optimal
and a whole family of enumeration problems inherits the lower bound. Because the argument is short and the claim is strong,
expert checking matters. Status: unrefereed.

## What is disputed or not yet verified

- Verification: Unrefereed preprint; checked by the authors

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 161 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 100 days after its cutoff
- Gemini 3.8 Flash (training cutoff March 2026): 191 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 130 days after its cutoff

## Sources

1. [Kobayashi, Kurita & Wasa: An ETH-based quasipolynomial lower bound for Dualization (arXiv 2610.11473)](https://arxiv.org/abs/2610.11473) (arxiv.org, paper)

## Changes

- 2026-10-09 (filed): Created from the arXiv PDF

## Related

- 2026-10-07: [Braverman & He refute the 2004 undirected multiple-unicast (network coding) conjecture with a GPT-6-found counterexample on PG(2, 9)](https://postcutoff.com/e/2026-10-07-multiple-unicast-conjecture-false-gpt-6/index.md)
- 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md)