The 4^k Barrier for the k-Distinct Language

Can the $k$-distinct language - words over $[n]$ of length at most $k$ with no repeated symbol - be recognized by an acyclic NFA of size $c^k n^{O(1)}$ for some $c < 4$? A construction of size $2^{1.96992k} n^{O(1)} < 3.918^k n^{O(1)}$ answers yes.

Result

Proved

Status

Resolved

AI contribution

AI co-developed

Method

Argument

Field

Parameterized automata

Posed by

Ran Ben-Basat, Ariel Gabizon & Meirav Zehavi

Year posed

2016

Years open

10y

Solved

2026-07-28

Model

ChatGPT / Codex 5.4-5.6 Pro, Gemini 3.1 Pro

Vendor

OpenAI / Google DeepMind

Collaborators

—

Verification

Unreviewed

Publication

Preprint

Significance

10 / 100*

Disclosed cost

—

Wikipedia

No dedicated article