[SDOI/SXOI2022] Little N's Independent Set

The question

Can the source-listed reference complexity O(n^2 k^4) be substantially improved?

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(n^{2} k^{4}\right)$
Latest reported AI result: $\mathcal{O}\!\left(k^{3} (n k)^{\log_{2} 3}\right)$

Normalized growth proxy · not benchmark data

This compares source-reported bounds; it is not a correctness or novelty finding.

Results

2026-09-12

Claimed result: $\mathcal{O}\!\left(k^{3} (n k)^{\log_{2} 3}\right)$

AI / model: Not identified

Reported method

The page keeps only the small gap d_u = W_u - N_u, records W_u in the polynomial degree, writes a heavy path as an ordered product of (k+1)x(k+1) polynomial matrices split at the weight midpoint, and multiplies with Karatsuba, giving a deterministic O((k+1)^3 (nk)^{log_2 3}) bound.

Verification

Source: Source reviewed
Theory: Theory not checked
Implementation: Code available
Prior art: Prior art not reviewed

The result page was opened and compared with the collection claim. Legacy audit state: audited_public.

The source reports its own keyword search (problem ID/name plus matrix, polynomial, NTT, divide-and-conquer, Karatsuba) found no identical approach, and explicitly says this does not prove priority. P02 performed no independent prior-art search, so prior_art_status stays unreviewed.

Credits

Published by: _endl_

Independent reproduction: Not yet performed

Prior-art review: Not yet performed