[BJWC2018] 最长上升子序列

问题

能否显著改进来源所列的 O(n × 2^n) or O(n p(n)) 参考复杂度？

算法前沿

参考前沿: $\mathcal{O}\!\left(n \times 2^{n}\right)\;\text{or}\;\mathcal{O}\!\left(n p(n)\right)$
最新所报 AI 结果: $\mathcal{O}\!\left(n^{23/12} \log^{2} n\right)$

归一化增长代理 · 非基准测量数据

此处比较的是来源所报复杂度，不构成正确性或原创性结论。

结果

2026-09-12

所报结果: $\mathcal{O}\!\left(n^{23/12} \log^{2} n\right)$

AI / 模型: ChatGPT

所述方法

源页面先将期望 LIS 长度化为 Gessel 行列式对应的生成函数递推，得到 O(n^3) 与 O(n^2 log n)；再对较大的 LIS 上界用 sigma-Painleve III 恒等式将状态压缩成有限维线性系统，最后将其写成一次矩阵递推，用乘积树与多点求值跳过绞大部分中间系数，声称得到 O(n^(23/12) log^2 n)。以上为源页面说法，本节点未验证其正确性。

核验

来源: 来源已查阅
理论: 理论未独立复核
实现: 仅理论结果 · 代码待补
前人工作: 未检索前人工作

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

源页面为 ChatGPT 分享链接，已读完。内联代码只对应 O(n^3) 版本；表中声称的 O(n^(23/12) log^2 n) 实现仅以已失效的 sandbox:/mnt/data/ 附件链接给出，因此实现状态保持“仅理论”。源页面自述仅做了本地对拍，明确说明不是在线评测记录。

问题

算法前沿

结果

所报结果: $\mathcal{O}\!\left(n^{23/12} \log^{2} n\right)$

所述方法

核验

署名与贡献

来源与历史

来源与历史

参与