GPT-6 Astra 把竞赛题复杂度从 O(n√n) 降到 O(n² polylog n)
知乎整理称 Astra 改进了 2018 年一道最长递增子序列题的已知最优复杂度，并引发选手用模型重刷更多「已最优」解法。
GPT-6 Astra Just Broke a Long-Standing Complexity Bound GPT-6 Astra reduced a competitive programming problem from O(np(n)) to O(n² polylog n), far beyond what contestants had long considered optimal. The bigger shift is that frontier models are now producing algorithms whose mathematics can take experts significant time to unpack. Zhihu contributor chenzhe, who published the original roundup, says the change became clear this year. During verification for the highly difficult CCPC Final, GPT Pro quickly solved all 13 problems, while even top human teams completed only 7 to 9 in competition. The new result came from a 2018 longest increasing subsequence problem. After Astra found the improved complexity, contestants began testing more problems with Astra and GPT-5.6 Sol, uncovering further improvements to supposedly best-known solutions. For chenzhe, this does not make competitive programming pointless. It changes the reason to learn it. The lasting value is in defining problems precisely, finding counterexamples, proving why a method works, revising failed ideas, and judging whether an AI-generated solution can be trusted.