The $4^k$ barrier for the $k$-distinct language

The problem asks whether the $k$-distinct language has an acyclic NFA of size $c^k n^{O(1)}$ for some $c<4$. In 2014, the optimal base was explicitly described as open.

Known results

• Ben-Basat, Gabizon, and Zehavi: an acyclic NFA of size $O^*(4^k k^{O(\log^2 k)})$.
• The same 2014 work records a lower bound of $2^k$ states for every NFA.

2026 barrier-breaking construction

The preprint Breaking the $4^k$ Barrier for the $k$-Distinct Language gives, for every $1\leq k\leq n$, a deterministically constructible acyclic NFA with $|Q|+|\Delta|\leq 2^{1.96992k}n^{O(1)}<3.918^k n^{O(1)}$. Its fixed-histogram stage already gives $O^*(3.967^k)$; compose-and-compress yields the final bound.

Current status (as of 2026): The existence of an acyclic NFA with size $c^k n^{O(1)}$ for some $c<4$ is established by the cited arXiv preprint; sharper constants and optimality remain open.